思路完全一样
AC的代码：
class Solution {
private:
struct Point {
int x, y;
Point(int _x, int _y):x(_x), y(_y) {}
};
public:
void solve(vector<vector<char> > & board) {
const int M = board.size();
if (M <= ) return;
const int N = board[].size();
vector<Point> run; // 没被包含的O，判断后修改为D来标记
for (int i=; i<M; ++i) // 1 边界
for (int j=; j<N; ++j)
if ((i== || i==M- || j== || j==N-) && board[i][j]=='O') {
board[i][j] = 'D';
run.push_back(Point(i, j));
}
const static int PATH[][] = {{,},{,-},{-,},{,}};
while (!run.empty()) { // 2 out -> insider
Point p = run.back();
run.pop_back();
for (int i=; i<; ++i) {
int x = p.x+PATH[i][];
int y = p.y+PATH[i][];
if (x< || x>=M || y< || y>= N || board[x][y]!='O')
continue;
board[x][y] = 'D';
run.push_back(Point(x, y));
}
}
for (int i=; i<M; ++i) // 3 检查
for (int j=; j<N; ++j) {
if (board[i][j]=='X') continue;
board[i][j] = (board[i][j]=='O'?'X':'O');
}
}
};
时间通不过的代码：
class Solution {
public:
void solve(vector<vector<char>> &board) {
int size = board.size();
if (size < )
return;
for (int j = ; j < size; ++j) {
if (board[][j] == 'O') {
board[][j] == '';
judgeRegion(board, , j);
}
if (board[size-][j] == 'O') {
board[size-][j] == '';
judgeRegion(board, size-, j);
}
}
for (int i = ; i < size - ; ++i) {
if (board[i][] == 'O') {
board[i][] == '';
judgeRegion(board, i, );
}
if (board[i][size-] == 'O') {
board[i][size-] == '';
judgeRegion(board, i, size - );
}
}
for (int i = ; i < size; ++i) {
for (int j = ; j < size; ++j) {
if (board[i][j] == 'O')
board[i][j] = 'X';
if (board[i][j] == '')
board[i][j] == 'O';
}
}
}
void judgeRegion(vector<vector<char>> &board, int i, int j) {
int size = board.size();
if (i >= && j < size && board[i][j] == 'O') {
board[i][j] == '';
judgeRegion(board, i-, j);
judgeRegion(board, i+, j);
judgeRegion(board, i, j-);
judgeRegion(board, i, j+);
}
}
};