# Why my code is so slowly? Using DFS 40ms.

• ``````class Solution {
public:
void solve(vector<vector<char>>& board)
{
if (board.size() == 0)
return;
if (board[0].size() == 0)
return;

std::vector<std::vector<bool>> visited(board.size(), std::vector<bool>(board[0].size(), false));

// top
for (int i = 0; i < board[0].size(); ++i)
dfs(board, 0, i, visited, true);
// bottom
for (int i = 0; i < board[0].size(); ++i)
dfs(board, board.size() - 1, i, visited, true);
// left
for (int i = 0; i < board.size(); ++i)
dfs(board, i, 0, visited, true);
// right
for (int i = 0; i < board.size(); ++i)
dfs(board, i, board[0].size() - 1, visited, true);

// the rest point
for (int i = 1; i < board.size() - 1; ++i)
for (int j = 1; j < board[i].size() - 1; ++j)
{
if (!visited[i][j] && board[i][j] == 'O')
board[i][j] = 'X';
}
}

private:
void dfs(std::vector<std::vector<char>> &board, int row, int col, std::vector<std::vector<bool>> &visited, bool isAtBounder)
{
if (row < 0 || row >= board.size())
return;
if (col < 0 || col >= board[row].size())
return;
if (visited[row][col])
return;

stack<pair<int, int>> stk;
stk.push(make_pair(row, col));

while (!stk.empty())
{
pair<int, int> point = stk.top();
stk.pop();

int i = point.first;
int j = point.second;

if (visited[i][j])
continue;

visited[i][j] = true;
if (board[i][j] == 'O')
{
if (!isAtBounder)
board[i][j] = 'X';

if (i - 1 >= 0 && i - 1 < board.size() && !visited[i - 1][j])
stk.push(make_pair(i - 1, j));
if (i + 1 >= 0 && i + 1 < board.size() && !visited[i + 1][j])
stk.push(make_pair(i + 1, j));
if (j - 1 >= 0 && j - 1 < board[row].size() && !visited[i][j - 1])
stk.push(make_pair(i, j - 1));
if (j + 1 >= 0 && j + 1 < board[row].size() && !visited[i][j + 1])
stk.push(make_pair(i, j + 1));
}
}
}
};``````

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