首页 > 代码库 > [leetcode]Surrounded Regions

[leetcode]Surrounded Regions

2024-07-16 08:47:01   214人阅读

Surrounded Regions

Given a 2D board containing ‘X‘ and ‘O‘, capture all regions surrounded by ‘X‘.

A region is captured by flipping all ‘O‘s into ‘X‘s in that surrounded region.

For example,

X X X XX O O XX X O XX O X X

 

After running your function, the board should be:

X X X XX X X XX X X XX O X X

算法思路：由外向内扫描，因为边界的O肯定是escape的，这样由边界往里面纵深查找出没有被capture的O

思路1：dfs，第一次居然过了，然后就再也过不去了，试想一个矩阵是100* 100并且全是O，如果dfs的话，就会有10000层，栈空间都溢出了....

思路2：BFS，大数据无压力过

代码如下：

 1 public class Solution { 2 public void solve(char[][] board) { 3         if(board == null || board.length == 0 ) return; 4         int height = board.length; 5         int width = board[0].length; 6         int code = Math.max(height, width); 7         for(int i = 0; i < height; i++){ 8             for(int j = 0; j < width; j++){ 9                 if(board[i][j] == ‘O‘ && (i == 0 || i == height - 1 || j == 0 || j == width - 1)){10                     board[i][j] = ‘@‘;11                     bfs(board, height, width, i, j, code);12                 }13             }14         }15         for(int i = 0; i < height; i++){16             for(int j = 0; j < width; j++){17                 if(board[i][j] == ‘O‘){18                     board[i][j] = ‘X‘;19                 }else if(board[i][j] == ‘@‘){20                     board[i][j] = ‘O‘;21                 }22             }23         }24     }25     int[][] dir = {{-1,0},{1,0},{0,1},{0,-1}};26     private void bfs(char[][] board,int height,int width,int i ,int j,int code){27         Queue<Integer> q = new LinkedList<Integer>();28         q.offer(i * code + j);//将二维下标压缩成一维，方便存储29         while(!q.isEmpty()){30             int tem = q.poll();31             int row = tem / code;32             int col = tem % code;33             for(int k = 0;k < dir.length; k++){34                 if(row + dir[k][0] < height && row + dir[k][0] >= 0 && col + dir[k][1] < width && col + dir[k][1] >= 0){35                     if(board[row + dir[k][0]][col + dir[k][1]] == ‘O‘){36                         board[row + dir[k][0]][col + dir[k][1]] = ‘@‘;37                         q.offer((row + dir[k][0]) * code + col + dir[k][1]);38                     }39                 }40             }41         }42     }43 }

坐标压缩法很有意思。

 


联系
我们