思路奇特, 逆向思维, 以四周上的’O’为突破口, 标记为访问过, 然后重新遍历数据, 将没有标记过得’O’变成X就可以了本质上还是一个4个方向的回溯, 可以说就是4叉树的遍历, 再本质点说就是个递归
class Solution {
public:
void solve(vector<vector<char>>& board) {
if (board.empty() || board[0].empty()) {
return;
}
int rows = board.size();
int cols = board[0].size();
vector<vector<bool>> visited(rows, vector<bool>(cols, false));
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if ((i == 0 || i == rows - 1 || j == 0 || j == cols - 1) && board[i][j] == 'O') {
dfs(board, rows, cols, i, j, visited);
}
}
}
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (board[i][j] == 'O' && !visited[i][j]) {
board[i][j] = 'X';
}
}
}
return;
}
void dfs(vector<vector<char>>& board, int rows, int cols, int i, int j, vector<vector<bool>>& visited) {
if (i < 0 || i >= rows || j < 0 || j >= cols || visited[i][j] || board[i][j] != 'O') {
return;
}
visited[i][j] = true;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
for (int idx = 0; idx < 4; idx++) {
i = i + dx[idx];
j = j + dy[idx];
dfs(board, rows, cols, i, j, visited);
i = i - dx[idx];
j = j - dy[idx];
}
}
};
Processed:
0.012, SQL:
8
