# C++ solution inspired from the game of I-go(20ms)

• I guess this question is inspired from Chinese traditional sport—I-go. Here the task is to flip all the dead pieces.

My solution is common: perform BFS from live pieces('O') on the edges and mark the live pieces with temporary state '+'. After BFS done, scan the whole board to flip remaining 'O' (dead) cells and recover live pieces('+') to 'O'.

``````class Solution {
public:
int row;
int col;
vector<pair<int, int> > move_step;

void bfs(vector<vector<char> > &board, int r, int c) {
queue<pair<int, int> > qe;
qe.push({r, c});

while(!qe.empty()) {
r = qe.front().first;
c = qe.front().second;
qe.pop();
for(int i = 0; i < 4; i++) {
int rr = r + move_step[i].first;
int cc = c + move_step[i].second;
if(rr >= 0 && rr < row
&& cc >= 0 && cc < col
&& board[rr][cc] == 'O') {
board[rr][cc] = '+';
qe.push({rr, cc});
}
}
}

return;
}

void solve(vector<vector<char> > &board) {
if (board.empty())
return;

row = board.size();
col = board[0].size();

move_step.resize(4);
move_step[0] = {0,-1};
move_step[1] = {0,1};
move_step[2] = {-1,0};
move_step[3] = {1,0};

// BFS from four edges and mark  non-surrounded(dead) cells with '+' sign

// top edge
for(int i = 0; i < col; i++) {
if(board[0][i] == 'O') {
board[0][i] = '+';
bfs(board, 0, i);
}
}

// bottom edge
for(int i = 0; i < col; i++) {
if(board[row-1][i] == 'O') {
board[row-1][i] = '+';
bfs(board, row-1, i);
}
}

// left edge
for(int i = 1; i < row-1; i++) {
if(board[i][0] == 'O') {
board[i][0] = '+';
bfs(board, i, 0);
}
}

// right edge
for(int i = 1; i < row-1; i++) {
if(board[i][col-1] == 'O') {
board[i][col-1] = '+';
bfs(board, i, col-1);
}
}

// then scan all the cells, recover live cells and flip dead cells
for(int i = 0; i < row; i++)
for(int j = 0; j < col; j++) {
char cur = board[i][j];
// recover live cell marked with '+' to 'O'
if(cur == '+')
board[i][j] = 'O';
// flip dead cell to '*'
else if(cur == 'O')
board[i][j] = 'X';
}

return;
}
};``````

• It took me 32ms to run your code :)

• I use a `queue<int>` instead of your `queue<pair>` and got a time limit exceeded.

I push 2 integers as a pair and pop 2 integers every iteration.

I'm a little confused.

``````class Solution {
public:
void solve(vector<vector<char> > &board) {
if (board.size() < 3) return;
if (board[0].size() < 3) return;
for (int i = 0; i < board[0].size(); i++) // search upside and downside
{
if (board[0][i] == 'O')
bfs(board, 0, i);
if (board[board.size()-1][i] == 'O')
bfs(board, board.size()-1, i);
}
for (int i = 1; i < board.size()-1; i++) // search right and left
{
if (board[i][0] == 'O')
bfs(board, i, 0);
if (board[i][board[0].size()-1] == 'O')
bfs(board, i, board[0].size()-1);
}
for (int i = 0; i < board.size(); i++)
for (int j = 0; j < board[i].size(); j++)
if (board[i][j] == '+')
board[i][j] = 'O';
else
board[i][j] = 'X';
}

void bfs(vector<vector<char> > &board, int row, int col)
{
queue<int> locs;
locs.push(row); // push row first then col
locs.push(col);
while (locs.empty() == false)
{
int i = locs.front(); // get row first then col
locs.pop();
int j = locs.front();
locs.pop();
board[i][j] = '+';
if (i > 0 && board[i-1][j] == 'O') {locs.push(i-1);locs.push(j);}
if (i+1 < board.size() && board[i+1][j] == 'O') {locs.push(i+1);locs.push(j);}
if (j > 0 && board[i][j-1] == 'O') {locs.push(i);locs.push(j-1);}
if (j+1 < board[0].size() && board[i][j+1] == 'O') {locs.push(i);locs.push(j+1);}
}
}
};``````

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