I have some issues when trying to understand the space complexity of problem 19.3 (Paint a Boolean Matrix).

The book says the space complexity of BFS is O(m+n) because there are at most O(m+n) vertices that are at the same distance from a given entry. However, I think a tighter estimation may be O(sqrt(m^2 + n^2)). For example, when the paint position starts at the corner and all the matrix is true, the max queue size is the diagonal, sqrt(m^2 + n^2). Also, when beginning at the center, the max queue size is twice of the diagonal, 2*sqrt(m^2 + n^2).

Moreover, the book does not say about the space complexity of DFS solution which I assume also the same with the BFS, O(m+n). However, the space complexity of the DFS is O(m*n), when the paint position starts at the corner and all the matrix is true. It would be much clearer if the book have a sentence about the space complexity.