[LeetCode][Java] Surrounded Regions
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了[LeetCode][Java] Surrounded Regions,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2471字,纯文字阅读大概需要4分钟。
内容图文
![[LeetCode][Java] Surrounded Regions](/upload/InfoBanner/zyjiaocheng/1327/3489e97921774594baf7c41db0596f4f.jpg)
题目:
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 X
X O O X
X X O X
X O X X
After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X
题意:
给定一个2维平面包含‘X‘
和 ‘O‘,填充所有的被
‘X‘
包围的区域
.
比如,
X X X X
X O O X
X X O X
X O X X
运行完你的函数后,这个平面变为:
X X X X
X O O X
X X O X
X O X X
算法分析:
* 典型的BFS题目。遍历每个字符,如果是“O”,则从当前字符开始BFS遍历,如果周围也是“O”则加入当前遍历的队列,
* 直到遍历完所有相邻的“O”,于此同时,判断每个O是否是被包围的,只要由一个O是没有被包围的,
* 则当前遍历的O的集合都是没有被包围的,因为这些O都是相连的。
AC代码:
<span style="font-family:Microsoft YaHei;font-size:12px;">public class Solution { public void solve(char[][] board) { if(board==null||board.length==0) return; int row=board.length; int col=board[0].length; boolean visited[][] = new boolean[row][col] ;//遍历标记数组 for(int i=0;i<row;i++) { for(int j=0;j<col;j++) { if(board[i][j]=='O'&&(!visited[i][j])) { bfs(board,i,j,visited);//若未遍历过,则对该节点进行广度优先搜索 } } } } private void bfs(char[][] board,int i,int j,boolean visited[][]) { ArrayList<Integer> list =new ArrayList<Integer>(); Queue<Integer> queue = new LinkedList<Integer>(); boolean label=true; int row=board.length; int col=board[0].length; int temjudge,temi,temj; queue.add(i*col+j);//将数组位置二维转化为一维 visited[i][j]=true; while(!queue.isEmpty()) { temjudge=queue.poll(); list.add(temjudge); temj=temjudge%col;//列位置 temi=(temjudge-temj)/col;//行位置 if(temi==0||temj==0||temi==row-1||temj==col-1) label=false;//若该节点位于边界处,这是没有被围,所以遍历到的所有节点都不变化,这里用label记录一下 if(temj>0&&board[temi][temj-1]=='O'&&!visited[temi][temj-1])//左 { queue.add(temi*col+temj-1); visited[temi][temj-1]=true; } if(temi>0&&board[temi-1][temj]=='O'&&!visited[temi-1][temj])//上 { queue.add((temi-1)*col+temj); visited[temi-1][temj]=true; } if(temj<board[0].length-1&&board[temi][temj+1]=='O'&&!visited[temi][temj+1])//右 { queue.add(temi*col+temj+1); visited[temi][temj+1]=true; } if(temi<board.length-1&&board[temi+1][temj]=='O'&&!visited[temi+1][temj])//下 { queue.add((temi+1)*col+temj); visited[temi+1][temj]=true; } } if(label)//遍历到的所有的节点都没有处于边界,这是对这些节点进行变化 { for(int k=0;k<list.size();k++) { temjudge=list.get(k); temj=temjudge%col; temi=(temjudge-temj)/col; board[temi][temj]='X'; } } } }</span>
版权声明:本文为博主原创文章,转载注明出处
原文:http://blog.csdn.net/evan123mg/article/details/47132935
内容总结
以上是互联网集市为您收集整理的[LeetCode][Java] Surrounded Regions全部内容,希望文章能够帮你解决[LeetCode][Java] Surrounded Regions所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。