leetcode shttps://oj.leetcode.com/problems/surrounded-regions/

1.从外围搜索O，深度搜索出现了

Line 35: java.lang.StackOverflowError
Last executed input:	["OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO

 1 public class Solution {
 2     public void solve(char[][] board) {
 3         if(board.length==0) return;
 4         int len1=board.length;
 5         int len2=board[0].length;
 6         for(int i=0;i<len1;i++)
 7         {
 8             if(board[i][0]=='O') dfs(board,i,0);
 9             if(board[i][len2-1]=='O') dfs(board,i,len2-1);
10             
11         }
12         for(int i=0;i<len2;i++)
13         {
14             
15             if(board[0][i]=='O')dfs(board,0,i);
16             if(board[len1-1][i]=='O')dfs(board,len1-1,i);
17         }
18         for(int i=0;i<len1;i++)
19         {
20             for(int j=0;j<len2;j++)
21             {
22                 if(board[i][j]=='h') board[i][j]='O';
23                 else  board[i][j]='X';
24             }
25         }
26         
27         
28     }
29     public void dfs(char b[][],int i,int j)
30     {
31         if(i<0||i>b.length-1||j<0||j>b[0].length-1) return;
32         if(b[i][j]!='O') return;
33         
34           if(b[i][j]=='O') b[i][j]='h';
35           dfs(b,i+1,j);//up
36           dfs(b,i-1,j);//down
37           dfs(b,i,j+1);//left
38           dfs(b,i,j-1);//right;
39          
40         
41     }
42 }

View Code

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]));
            }
            
            
            
        }
        
        }

}