dfs过得太蹊跷了,本博文算法作废,新博文地址:[leetcode]Surrounded Regions
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 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
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
有点像围棋——一旦把你全部围住,就把你的棋子全部变成我的。
刚开始看这道题的时候,考虑的过于简单了:先遍历整个棋盘,遇到O则上下左右找X,如果四个方向都找到了X,则表示该O可以被替换。这显然是不对的。
比如:
{ 'O','X','X','O','X'},
{ 'X','O','O','X','O'},
{ 'X','O','X','O','X'},
{ 'O','X','O','O','O'},
{ 'X','X','O','X','O'}
{ 'X','O','O','X','O'},
{ 'X','O','X','O','X'},
{ 'O','X','O','O','O'},
{ 'X','X','O','X','O'}
红圈圈上下左右都能找到X,但是还是可以沿着黄色的路径突围,因为我将这道题解释为escape 或者 find the way out。首先定义什么情况下才能escape或者find a way out:找到一条出路,可以走到棋盘的边界。
比如上图中黄色这条路。
因此我第二种做法是对于矩阵中的每一个O,用DFS看其是否能找到一个出路。 后来发现,比如上面的矩阵,当找不到出路时候,回溯比较麻烦,而且当矩阵比较大的时候,做的无用功可能太多了,可能导致超时。
因此我的第三种做法是先确定每一个可能的出口,然后根据出口找出路上的节点。
1.即先找到边界上的O点,如果矩阵中escap的棋子,必须经过这些O点才能escape。
2.从边界上的O点进行DFS,找到所有escapde的棋子。将escape的点做出标记。
3.然后再次遍历矩阵,对那些未作出标记的O点,设置为X即可。
代码如下
public void solve(char[][] board) { if (board == null || board.length == 0) { return; } int height = board.length; int width = board[0].length; boolean[][] visit = new boolean[height][width]; for(int i = 0 ; i < width; i++){ if(board[0][i] == 'O') visit[0][i] = true; if(board[height - 1][i] == 'O') visit[height - 1][i] = true; } for(int i = 0 ; i < height; i++){ if(board[i][0] == 'O') visit[i][0] = true; if(board[i][width - 1] == 'O') visit[i][width - 1] = true; } for(int i = 0 ; i < visit.length; i++){ for(int j = 0; j < visit[0].length;j++){ if(visit[i][j]){ dfs(board, visit, i, j); } } } for(int i = 1; i < height; i++){ for(int j = 1; j < width; j++){ if(board[i][j] == 'O' && !visit[i][j]){ board[i][j] = 'X'; } } } } private void dfs(char[][] board,boolean[][] visit,int i ,int j){ visit[i][j] = true; if(i > 0 && board[i - 1][j] == 'O' && !visit[i - 1][j]){ dfs(board, visit, i - 1, j); } if(i < visit.length - 1 && board[i + 1][j] == 'O' && !visit[i + 1][j]){ dfs(board, visit, i + 1, j); } if(j > 0 && board[i][j - 1] == 'O' && !visit[i][j - 1]){ dfs(board, visit, i, j - 1); } if(j < visit[0].length - 1 && board[i][j + 1] == 'O' && !visit[i][j + 1]){ dfs(board, visit, i, j + 1); } }
相关推荐
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
大佬的leetcode刷题笔记(c++版本)
vs code LeetCode 插件
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
leetcode中文版
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101_源码.zip
100个leetCode详细解答
LeetCode 刷题汇总1
LeetCode 选讲1
terminal-leetcode, 终端Leetcode是基于终端的Leetcode网站查看器 终端 leetcode终端leetcode是基于终端的leetcode网站查看器。本项目是由 RTV 激发的。 我最近正在学习本地化的反应,以实践我的新知识,并根据这个...
leetcode刷题, 直接用leetcode的分类方式.
该分类为结合《算法导论》的内容,给出Leetcode题目分类。题目主要集中在Leetcode的前400题中,也包括有后面的一些经典值得刷的题。该题目分类按照算法和数据结构排版,即可供单独Leetcode刷题使用,也可以配合学习...
这份文档列出了leetcode几乎所有题目(大约134题)的分类以及难度指示,是刷leetcode的必备良品。现在leetcode总的题目数已经达到150题,所以有部分题目没有包含在这个文档中,但是——足够了。po主刷leetcode的时候...
leetcode高频面试笔试题150+道,亲身总结。
LeetCode面试笔试题
LeetCode 刷题笔记
(C++)LeetCode刷题题解答案
LeetCode 刷题
leetcode全套解答python版本。包括更新到10月份的的leetcode
这个是leetcode发布的ebook 包含有常见题目的解答以及讲解