1.从外围搜索O，深度搜索出现了
| Line 35: java.lang.*Error | |
| Last executed input: | ["OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO |
public class Solution {
public void solve(char[][] board) {
if(board.length==0) return;
int len1=board.length;
int len2=board[0].length;
for(int i=0;i<len1;i++)
{
if(board[i][0]=='O') dfs(board,i,0);
if(board[i][len2-1]=='O') dfs(board,i,len2-1);
}
for(int i=0;i<len2;i++)
{
if(board[0][i]=='O')dfs(board,0,i);
if(board[len1-1][i]=='O')dfs(board,len1-1,i);
}
for(int i=0;i<len1;i++)
{
for(int j=0;j<len2;j++)
{
if(board[i][j]=='h') board[i][j]='O';
else board[i][j]='X';
}
}
}
public void dfs(char b[][],int i,int j)
{
if(i<0||i>b.length-1||j<0||j>b[0].length-1) return;
if(b[i][j]!='O') return;
if(b[i][j]=='O') b[i][j]='h';
dfs(b,i+1,j);//up
dfs(b,i-1,j);//down
dfs(b,i,j+1);//left
dfs(b,i,j-1);//right;
}
}
2.广度搜索一定可以了。抽空在写，（可惜不行，我太水了超时代码）
class node
{
int x;
int y;
char c;
node(int x1,int y1,char c1)
{
x=x1;
y=y1;
c=c1; }
} public class Solution {
public void solve(char[][] board) {
if(board.length==0) return;
int len1=board.length;
int len2=board[0].length;
for(int i=0;i<len1;i++)
{
if(board[i][0]=='O') bfs(board,i,0);
if(board[i][len2-1]=='O') bfs(board,i,len2-1); }
for(int i=0;i<len2;i++)
{ if(board[0][i]=='O')bfs(board,0,i);
if(board[len1-1][i]=='O')bfs(board,len1-1,i);
}
for(int i=0;i<len1;i++)
{
for(int j=0;j<len2;j++)
{
if(board[i][j]=='h') board[i][j]='O';
else board[i][j]='X';
}
} }
public boolean is(int i,int j,int len1,int len2,char c[][])
{
if(i>=0&&i<len1&&j>=0&&j<len2&&c[i][j]=='O') return true;
return false;
} //put the o to h
public void bfs(char b[][],int i,int j)
{
int len1=b.length;
int len2=b[0].length;
Queue<node> queue=new LinkedList<node>(); queue.offer(new node(i,j,b[i][j]));
while(!queue.isEmpty())
{
node n1=queue.poll();
b[n1.x][n1.y]='h'; if(is(n1.x,n1.y+1,len1,len2,b))
{ queue.offer(new node(n1.x,n1.y+1,b[n1.x][n1.y+1]));
}
if(is(n1.x,n1.y-1,len1,len2,b))
{ queue.offer(new node(n1.x,n1.y-1,b[n1.x][n1.y-1]));
}
if(is(n1.x+1,n1.y,len1,len2,b))
{ queue.offer(new node(n1.x+1,n1.y,b[n1.x+1][n1.y]));
}
if(is(n1.x-1,n1.y,len1,len2,b))
{ queue.offer(new node(n1.x-1,n1.y,b[n1.x-1][n1.y]));
} } } }