Why my solution is Time Limit Exceeded

• I use BFS instead of DFS but still get TLE

``````void Solution::markSurround(vector<vector<char>> &board, int i, int j, int row, int col)
{
board[i][j] = '#';
queue<int> bfs;
bfs.push(i * col + j);

while (!bfs.empty())
{
int index = bfs.front();
bfs.pop();
int m = index / col;
int n = index % col;
board[m][n] = '#';
if (m > 0 && board[m - 1][n] == 'O')
{
bfs.push((m - 1) * col + n);
}
if (m < row - 1 && board[m + 1][n] == 'O')
{
bfs.push((m + 1) * col + n);
}
if (n > 0 && board[m][n - 1] == 'O')
{
bfs.push(m * col + n - 1);
}
if (n < col - 1 && board[m][n + 1] == 'O')
{
bfs.push(m * col + n + 1);
}
}
}

void Solution::solve(vector<vector<char>> &board) {
int row = board.size();
if (row < 3)
{
return;
}
int col = board[0].size();
for (int j = 0; j < col; j++)
{
if (board[0][j] == 'O')
{
markSurround(board, 0, j, row, col);
}
if (board[row - 1][j] == 'O')
{
markSurround(board, row - 1, j, row, col);
}
}
for (int i = 0; i < row; i++)
{
if (board[i][0] == 'O')
{
markSurround(board, i, 0, row, col);
}
if (board[i][col - 1] == 'O')
{
markSurround(board, i, col - 1, row, col);
}
}

for (int i = 0; i < row; i++)
{
for (int j = 0; j < col; j++)
{
if (board[i][j] == '#')
{
board[i][j] = 'O';
}
else
{
board[i][j] = 'X';
}
}
}
}``````

• In your bfs solution, you did `board[m][n] = '#';` when get it from your bfs queue. However, it should be done when this position append to this queue, or there will be large duplicated elements in it.

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