将内部的O点变成X
input
X X X X
X O O X
X X O X
X O X X
output
X X X X
X X X X
X X X X
X O X X
DFS的基本框架是
void dfs(int now,int d){
if(终止条件) {
做相应的操作;
return;
}
for(遍历所有now点的相邻点next){
if(!visit[next]) {
访问每个没有访问过的点;
做相应的操作;
dfs(next, d + );
}
}
}
DFS图所有边上的点，将边上的O以及其联通域变为T，然后将内部的O变为X,外部的T变为O，本质是种子填充算法。
此题对于is_in这个函数要注意， 不要用(x < m) && (x >= 0) && (y < n) && (y >= 0) 会堆栈溢出！！原因是会出现边上的点全是O。。。
class Solution {
public:
int m, n;
bool is_in(int x, int y)
{
return (x < m-) && (x >= ) && (y < n-) && (y >= );
}
void dfs(std::vector<std::vector<char>> &board,int x,int y)
{
//if (!(is_in(x, y) && board[x][y] == 'O')) return;
//printf("%d %d\n", x, y);
board[x][y] = 'T';
int dir[][] = { { , }, { -, }, { , }, { , - } };
for (int i = ; i < ; ++i){
int tx = x + dir[i][];
int ty = y + dir[i][];
if (is_in(tx, ty) && board[tx][ty] == 'O')
{
dfs(board, tx, ty);
}
}
}
void change(std::vector<std::vector<char>> &board)
{
for (int i = ; i < m;++i){
for (int j = ; j < n;++j){
if (board[i][j] == 'T') board[i][j] = 'O';
else if (board[i][j] == 'O') board[i][j] = 'X';
else;
}
}
}
void solve(std::vector<std::vector<char>> &board)
{
m = board.size();
if (m == ) return;
n = board[].size();
if (n == ) return;
for (int i = ; i < m;++i){
if (board[i][] == 'O') dfs(board, i, );
if (board[i][n - ] == 'O') dfs(board, i, n-);
}
for (int i = ; i < n; ++i){
if (board[][i] == 'O') dfs(board, , i);
if (board[m-][i] == 'O') dfs(board, m-, i);
}
change(board);
}
};