爱华网
这题就是基本的DFS／BFS加入一些变形，用DFS／BFS都可以解。我两种方法都写了一下，DFS要简洁一些。
DFS:
public class Solution {
int m,n;
char[][]board;
void dfs(int x,int y){
if(x<0 ||x>=m || y<0 || y>=n ||board[x][y]!='O') return;
board[x][y]='D';
dfs(x-1,y);
dfs(x+1,y);
dfs(x,y-1);
dfs(x,y+1);
}
public voidsolve(char[][] board){
if(board==null ||board.length==0) return;
this.board=board;
m=board.length;
n=board[0].length;
for(intj=0;j<n;j++){
dfs(0,j);
dfs(m-1,j);
}
for(inti=1;i<m-1;i++){
dfs(i,0);
dfs(i,n-1);
}
for(inti=0;i<m;i++)
for(int j=0;j<n;j++){
if(board[i][j]=='O') board[i][j]='X';
elseif(board[i][j]=='D') board[i][j]='O';
}
}
}
BFS:public class Solution { int m,n; char[][] board; Queue<Integer> queue=newLinkedList<Integer>(); void fill(int x, inty){ if(x<0 || x>=m ||y<0 || y>=n || board[x][y]!='O')return; queue.offer(x*m+y); board[x][y]='D'; } void bfs(int x, inty){ fill(x,y); while(!queue.isEmpty()){ intcurr=queue.poll(); inti=curr/n; intj=curr%n; fill(i-1,j); fill(i+1,j); fill(i,j-1); fill(i,j+1); } } public voidsolve(char[][] board){ if(board==null || board.length==0) return; this.board=board; m=board.length; n=board[0].length; for(int j=0;j<n;j++){ bfs(0,j); bfs(m-1,j); } for(int i=1;i<m-1;i++){ bfs(i,0); bfs(i,n-1); } for(int i=0;i<m;i++) for(intj=0;j<n;j++){ if(board[i][j]=='O')board[i][j]='X'; else if(board[i][j]=='D')board[i][j]='O'; } }}
博主对本博客文章及代码享有著作权。网络转载请注明出处http://blog.sina.com.cn/leetcode。整理出版物请和作者联系。
