p*****p
发帖数: 379 | 1 用checked标记封闭的区域，用markChecked把O变成X
small能过，large挂了，莫非是因为偷懒用dfs造成溢出了？
class Solution {
public:
void solve(vector> &board) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (board.size() <= 1) return;
int rows = board.size();
int cols = board[0].size();
vector> visited(rows, vector(cols, false));
vector> checked(rows, vector(cols, false));
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
if (!visited[i][j]) {
if (board[i][j] == 'O') {
if (checkIfSurrounded(i, j, board, visited, checked)
) {
markChecked(i, j, board, checked);
}
}
else {
visited[i][j] = true;
}
}
}
}
}
bool checkIfSurrounded(int i, int j, vector> &board,
vector> &visited, vector> &checked) {
if (visited[i][j]) return true;
visited[i][j] = true;
bool left = false, right = false, up = false, down = false;
if (j - 1 >= 0) {
if (board[i][j - 1] == 'X') {
left = true;
}
else {
left = checkIfSurrounded(i, j - 1, board, visited, checked);
}
}
if (j + 1 < board[0].size()) {
if (board[i][j + 1] == 'X') {
right = true;
}
else {
right = checkIfSurrounded(i, j + 1, board, visited, checked);
}
}
if (i - 1 >= 0) {
if (board[i - 1][j] == 'X') {
up = true;
}
else {
up = checkIfSurrounded(i - 1, j, board, visited, checked);
}
}
if (i + 1 < board.size()) {
if (board[i + 1][j] == 'X') {
down = true;
}
else {
down = checkIfSurrounded(i + 1, j, board, visited, checked);
}
}
bool result = left && right && up && down;
if (result) {
checked[i][j] = true;
}
return result;
}
void markChecked(int i, int j, vector> &board,
vector> &checked) {
if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size()) {
return;
}
if (checked[i][j]) {
checked[i][j] = false;
board[i][j] = 'X';
markChecked(i, j - 1, board, checked);
markChecked(i, j + 1, board, checked);
markChecked(i - 1, j, board, checked);
markChecked(i + 1, j, board, checked);
}
}
}; |
