# DFS with off-by-one problem

• I just tried to solve this question with both BFS and DFS, and BFS worked while DFS failed.

It's weird that, if I submitted this solution, I would get run-time error, however, if I copied the test case to costum testcase, it worked fine.

I thought that my logic should be right, the process was similar to the BFS solution. Then I tried to compare the DFS one with my accepted solutoin, which was submitted several months ago, I found there was just an off-by-one problem. Here is my DFS solution with runtime error:

``````class Solution {
private:
// change x< 0 and y < 0 to x < 1, y < 1
bool check(vector<vector<char>>& board, int x, int y, int m, int n) {
return !(x < 0 || y < 0 || x >= m || y >= n || board[x][y] != 'O');
}
void dfs(vector<vector<char>>& board, int x, int y, int m, int n, vector<vector<int>>& dir) {
for (int i = 0; i < 4; i++) {
int nx = x + dir[i][0], ny = y + dir[i][1];
if (check(board, nx, ny,  m, n)) {
board[nx][ny] = '#';
dfs(board, nx, ny, m, n, dir);
}
}
}
public:
void solve(vector<vector<char>>& board) {
if (board.size() == 0 || board[0].size() == 0) return;
int m = board.size(), n = board[0].size();
vector<vector<int>> dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
// Add all outside 'O' to our queue
queue<pair<int, int>> q;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// Just need one of the bound
if (board[i][j] == 'O' && !(i != 0 && j != 0 && i != m - 1 && j != n - 1)) {
board[i][j] = '#';
dfs(board, i, j, m, n, dir);
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == '#') board[i][j] = 'O';
else if (board[i][j] == 'O') board[i][j] = 'X';
}
}
}
};
``````

After I changed

x < 0 || y < 0

to be

x < 1 || y < 1

in the boundary checking function, it was accepted. I understand that, since we will call the dfs from the boundary of the matrix, we no longer need to check it again, but how to explain the runtime error if I just want to check it again? Anyone have any idea?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.