首页 > 代码库 > [Leetcode][JAVA] Surrounded Regions
[Leetcode][JAVA] 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
基本思路是：如果把所有不该变为X的O标注出来，那么剩下的O就是要变为X的了。
所以，从矩阵各个边上的O开始进行图的遍历，入栈/队列时把相应节点值从‘O‘变成其他符号（我用的是‘+‘）,出栈/队列时对节点四方的相邻值为‘O‘的节点进行讨论。
全部遍历完后，把‘O‘变为‘X‘， ‘+‘变为‘O‘。
代码：
1 public class Pair { 2 int x; 3 int y; 4 Pair(int x, int y) { 5 this.x = x; 6 this.y = y; 7 } 8 } 9 public void solve(char[][] board) {10 int m=board.length;11 if(m<=2)12 return;13 int n=board[0].length;14 for(int i=0;i<m;i++) {15 if(board[i][0]==‘O‘)16 dfs(board, i, 0);17 if(board[i][n-1]==‘O‘)18 dfs(board, i, n-1);19 }20 for(int i=0;i<n;i++) {21 if(board[0][i]==‘O‘)22 dfs(board, 0, i);23 if(board[m-1][i]==‘O‘)24 dfs(board, m-1, i);25 }26 for(int i=0;i<m;i++)27 for(int j=0;j<n;j++) {28 if(board[i][j]==‘O‘)29 board[i][j]=‘X‘;30 else if(board[i][j]==‘+‘)31 board[i][j]=‘O‘;32 }33 }34 public void dfs(char[][] bd, int i, int j)35 {36 Stack<Pair> st = new Stack<Pair>();37 bd[i][j] = ‘+‘;38 st.push(new Pair(i,j));39 40 while(!st.isEmpty()) {41 Pair temp = st.pop();42 if(temp.x>0 && bd[temp.x-1][temp.y]==‘O‘) {43 bd[temp.x-1][temp.y]=‘+‘;44 st.push(new Pair(temp.x-1, temp.y));45 }46 if(temp.y<bd[0].length-1 && bd[temp.x][temp.y+1]==‘O‘) {47 bd[temp.x][temp.y+1]=‘+‘;48 st.push(new Pair(temp.x, temp.y+1));49 }50 if(temp.x<bd.length-1 && bd[temp.x+1][temp.y]==‘O‘) {51 bd[temp.x+1][temp.y]=‘+‘;52 st.push(new Pair(temp.x+1, temp.y));53 }54 if(temp.y>0 && bd[temp.x][temp.y-1]==‘O‘) {55 bd[temp.x][temp.y-1]=‘+‘;56 st.push(new Pair(temp.x, temp.y-1));57 }58 }59 }
[Leetcode][JAVA] Surrounded Regions
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。