# Cannot pass due to time limit, but already changed to queue

• Hi, can anyone help me take a look at my solution? I already changed from recursive to iterative, but still cannot pass due to time limit. How can I further improve it?

``````class Solution {
public:
struct Node {
int x, y;
Node(int x_, int y_) : x(x_), y(y_) {}
};

void mark(vector<vector<char> > &board, Node cur) {
if (board[cur.x][cur.y] == 'X' || board[cur.x][cur.y] == '+') { return; }

queue<Node> q;
q.push(cur);

while (!q.empty()) {
Node tmp = q.front(); q.pop();
board[tmp.x][tmp.y] = '+';

if (tmp.x > 0 && board[tmp.x-1][tmp.y] == 'O') { q.push(Node(tmp.x-1, tmp.y)); }
if (tmp.y > 0 && board[tmp.x][tmp.y-1] == 'O') { q.push(Node(tmp.x, tmp.y-1)); }
if (tmp.x < board.size()-1 && board[tmp.x+1][tmp.y] == 'O') { q.push(Node(tmp.x+1, tmp.y)); }
if (tmp.y < board[0].size()-1 && board[tmp.x][tmp.y+1] == 'O') { q.push(Node(tmp.x, tmp.y+1)); }
}
}

void solve(vector<vector<char> > &board) {
if (board.size() == 0 || board[0].size() == 0) { return; }
int m = board.size(), n = board[0].size();

for (int i = 0; i < m; ++i) {
if (board[i][0] == 'O') { mark(board, Node(i, 0)); }
if (board[i][n-1] == 'O') { mark(board, Node(i, n-1)); }
}

for (int j = 1; j < n-1; ++j) {
if (board[0][j] == 'O') { mark(board, Node(0, j)); }
if (board[m-1][j] == 'O') { mark(board, Node(m-1, j)); }
}

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'; }
}
}
``````

};

• ``````        board[tmp.x][tmp.y] = '+';
``````

By setting board[tmp.x][tmp.y]='+' after you have popped it out of the queue, you are leaving a lot of scope of repeated entries.
You should set this value to '+' while you are pushing it into your queue.

• Yes, you are right. I made the same mistake and can't find why I got TLE when use BFS.

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