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); } }
相关推荐
python python_leetcode题解之130_Surrounded_Regions
vs code LeetCode 插件
《Python版LeetCode题解全集详解》 LeetCode是一个广受欢迎的在线编程挑战平台,致力于帮助程序员提升技能,特别是面试准备。这个压缩包“lc-all-solutions-master”包含了使用Python语言解决LeetCode所有问题的...
《使用leetcode-editor在IDE中进行LeetCode练习的全方位指南》 LeetCode是一个广受欢迎的在线编程练习平台,它提供了一系列的算法题目供程序员们提升技能。对于习惯在集成开发环境(IDE)中工作的开发者来说,将...
3. **Surrounded Regions.cpp** - 第49题,解冑处理的是矩阵中的被包围的区域。通常需要使用深度优先搜索或广度优先搜索策略,通过连通组件的概念来解决这类问题。 4. **N-Queens.cpp** - 这是经典的第51题“N皇后...
"IDEA leetcode-editor插件"就是将这两者结合的工具,允许用户在IDEA中直接进行LeetCode的编程挑战,无需离开开发环境,提高了刷题的便捷性。 该插件的主要功能包括: 1. **离线模式**:在无法访问LeetCode官网的...
terminal-leetcode, 终端Leetcode是基于终端的Leetcode网站查看器 终端 leetcode终端leetcode是基于终端的leetcode网站查看器。本项目是由 RTV 激发的。 我最近正在学习本地化的反应,以实践我的新知识,并根据这个...
(C++)LeetCode刷题题解答案
leetcode刷题, 直接用leetcode的分类方式.
7. leetcode-130-Surrounded-Regions.md:第130题,包围的区域,可能涉及二维数组处理和深度优先搜索(DFS)。 8. leetcode-29-Divide-Two-Integers.md:第29题,两数相除,涉及到整数除法和位运算。 9. leetcode-...
### LeetCode中文版知识点概述 #### 一、LeetCode简介与使用 LeetCode是一个全球知名的在线编程学习平台,主要提供各种算法题目供开发者练习。它不仅涵盖了基础数据结构和算法训练,还包括了大量的面试真题,是...
LeetCode面试笔试题
基于Python实现的LeetCode爬虫爬取LeetCode题目描述和提交的代码.zip ## 特点 - 支持爬取题目列表,保存为本地CSV/Excel文件。 - 支持爬取题目描述,保存为本地HTML文件。 - 支持爬取用户提交的代码,保存为如_.py...
LeetCode-Swift, 快速LeetCode解决方案 LeetCodeLeetCode在线判断是一个包含很多收费算法的网站。 them Google Google Google Google LinkedIn this this repo 。 请免费参考并收费STAR以支持这个 repo,
leetcode 习题集, leetcode 官网出品,包含基本的算法
《LeetCode经典题目全解析》是一份由编程高手精心编撰的文档,旨在全面解析LeetCode平台上众多的算法挑战题目。LeetCode作为一个知名的在线编程练习平台,汇集了各种难度级别的编程题目,涵盖数据结构、算法、设计...
LeetCode 400题目 Java版本 (LeetCode is the platform to help you enhance your skills, expand your knowledge and prepare for technical interviews.)
Source file for LeetCode Permutations Problem
《LeetCode Editor 7.4:提升编程技能的利器》 在编程学习和实践中,LeetCode 已经成为了程序员们磨炼算法、提升编程技能的重要平台。为了方便开发者更高效地进行刷题,LeetCode 提供了官方编辑器插件——LeetCode ...
leetcode算法。本书包含了 LeetCode Online Judge(http://leetcode.com/onlinejudge) 所有题目的答案,所有 代码经过精心编写,编码规范良好,适合读者反复揣摩,模仿,甚至在纸上默写。 全书的代码,使用 C++ 11 的...