Just imagine you are searching in a maze. You can go from the exits, slash all the Os, then mark all the remaining Os as Xs, and revive the dead Os (`%`

). :p

```
class Solution {
private:
struct Point {
int x;
int y;
Point(int x_, int y_) : x(x_), y(y_) {}
};
public:
void solve(vector<vector<char>> &board) {
vector<Point> path;
for (int i = 0; i < board.size(); i++) {
for (int j = 0; j < board[i].size(); j++) {
// only deal with the border
if ((j != 0 && j != board[i].size() - 1) &&
(i != 0 && i != board.size() - 1)) {
continue;
}
if (board[i][j] != 'O') continue;
// find all the Os
board[i][j] = '%'; // Slash it.
path.push_back(Point(i, j));
while (!path.empty()) {
Point p = path.back();
path.pop_back();
if (p.x + 1 < board.size() && board[p.x+1][p.y] == 'O') {
board[p.x+1][p.y] = '%';
path.push_back(Point(p.x+1, p.y)); // down
}
if (p.y + 1 < board[p.x].size() && board[p.x][p.y+1] == 'O') {
board[p.x][p.y+1] = '%';
path.push_back(Point(p.x, p.y+1)); // right
}
if (p.x > 0 && board[p.x-1][p.y] == 'O') {
board[p.x-1][p.y] = '%';
path.push_back(Point(p.x-1, p.y)); // up
}
if (p.y > 0 && board[p.x][p.y-1] == 'O') {
board[p.x][p.y-1] = '%';
path.push_back(Point(p.x, p.y-1)); // left
}
}
}
}
for (int i = 0; i < board.size(); i++) {
for (int j = 0; j < board[i].size(); j++) {
if (board[i][j] == 'O') {
board[i][j] = 'X';
} else if (board[i][j] == '%') {
board[i][j] = 'O'; // Welcome back.
}
}
}
}
};
```