问题描述:
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
原问题链接:https://leetcode.com/problems/surrounded-regions/
问题分析
从问题描述中给定的条件来说,一开始有点难以找到一个解决的入口。对于矩阵中一个或者若干个被X字符包围的O字符,我们就需要找到一个方法来确定这些O字符是否确实被包围,而不是它们有连接的O字符出口。那么该怎么确定它有O字符的出口呢?从前面问题的描述里已经看到了,如果有O字符在矩阵的4个边上,如果我们有字符和这些字符相邻,那么就可以确定这些字符是和出口想通的,也就是说它们不可能被X字符包围。
现在问题就在于该怎么找到所有和这些出口字符相邻的字符呢?这就相当于一个动态扩展的过程了。如果我们碰到某个在出口的O字符,我们就需要去看它的周边的字符,如果有字符也是O,那么我们就要想办法标记这个字符,而且这个字符也将作为出口的一个连接,我们应该将这个字符的周边字符的情况继续考虑在内。按照这个过程,这就是一个图的遍历过程。我们可以考虑采用深度优先或者广度优先的方式来遍历。
既然我们访问过这些连接到出口的元素,我们就需要对它们做一个标记,防止它们被重复访问。在这里,我们可以采用将这些连接到出口的元素设置为另外一个特殊值的方式。这样在后面的访问里将它们重新设置成O就可以了。
从实现的角度来说,如果我们采用广度优先遍历的方式来处理,我们就需要一个队列,队列里应该记录我们当前访问的矩阵位置。该用什么来记录矩阵的位置呢?在java里对键值对类型的支持不太理想,我们可以引用AbstractMap.SimpleEntry这个类型。在最开始的时候我们程序遍历矩阵的4个边,将所有为O的元素加入到队列中,并将该位置的元素设置成别的值。剩下的就是用广度优先遍历不断的判断和加入新的符合条件的元素。
在遍历完之后,我们再遍历一遍矩阵,将设置成这个特殊值的元素设置回去,同时将找到的O元素设置为X,因为这些元素既然不能找到出口,肯定就可以被设置成X了。
按照这个思路,可以得到详细的代码实现如下:
import static java.util.AbstractMap.SimpleEntry; public class Solution { public void solve(char[][] board) { if(board == null || board.length == 0 || board[0].length == 0) return; int m = board.length, n = board[0].length; Queue<SimpleEntry<Integer, Integer>> queue = new LinkedList<>(); for(int i = 0; i < m; i++) { if(board[i][0] == 'O') { board[i][0] = 'A'; queue.add(new SimpleEntry<>(i, 0)); } if(board[i][n - 1] == 'O') { board[i][n - 1] = 'A'; queue.add(new SimpleEntry<>(i, n - 1)); } } for(int i = 0; i < n; i++) { if(board[0][i] == 'O') { board[0][i] = 'A'; queue.add(new SimpleEntry<>(0, i)); } if(board[m - 1][i] == 'O') { board[m - 1][i] = 'A'; queue.add(new SimpleEntry<>(m - 1, i)); } } while(!queue.isEmpty()) { SimpleEntry<Integer, Integer> entry = queue.remove(); int row = entry.getKey(); int col = entry.getValue(); addEntry(board, row - 1, col, queue); addEntry(board, row + 1, col, queue); addEntry(board, row, col - 1, queue); addEntry(board, row, col + 1, queue); } for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { if(board[i][j] == 'A') board[i][j] = 'O'; else if(board[i][j] == 'O') board[i][j] = 'X'; } } } private void addEntry(char[][] board, int row, int col, Queue<SimpleEntry<Integer, Integer>> queue) { if(inRange(row, col, board) && board[row][col] == 'O') { board[row][col] = 'A'; queue.add(new SimpleEntry<>(row, col)); } } private boolean inRange(int row, int col, char[][] board) { return row >= 0 && row < board.length && col >= 0 && col < board[0].length; } }
相关推荐
正确的姿势,学习的态度来刷 LeetCode:高效的代码、简洁的注释、精炼的总结。
leetcode 非官方顺序leetcode题解,主要代码为Python和C++。 leetcode 第1题: leetcode 第2题: leetcode 第3题: leetcode 第4题: leetcode 第5题: leetcode 第6题: leetcode 第7题: leetcode 第9题: ...
leetcode11 top 1. 位运算 LeetCode191 : 二进制位1的个数 LeetCode338 : 比特位运算 2. 字典树 LeetCode209 : 实现一个Trie结构 LeetCode79 : 单词搜索(判断单词是否出现在给定的网格中) LeetCode212 : 单词搜索II...
LeetCode::laptop:LeetCode解决方案
leetcode 答案 leetCode :keyboard:我的 Leetcode 解题答案
lru缓存leetcode 力码 涵盖了 Geeks for Geeks 和 Leet Code 的各种问题。 LeetCode 1 : 二和 (46_Easy) LeetCode 2 : 两个数字相加 (96_Medium) LeetCode 3 : 无重复字符的最长子串 (214_Medium) LeetCode 4 : 两个...
LeetCode 在LeetCode和其他编码平台上解决的问题的集合
leetcode :ice_cream: LeetCode Kindem 的个人 LeetCode 题解仓库,欢迎交流学习。 下面的目录中 $number 题号代表经典 LeetCode 题目,$number.$number 题号表示 LeetCode 面试题。 :receipt: 目录 统计 值 AC 的...
leetcode 分类 LeetCode :bouquet::bouquet::bouquet: 介绍 leetcode 题解,Issues 会记录 leetcode 解题之路,并使用 label 进行了分类。 目录 链表
Leetcode:Leetcode提交
LeetCode 101:和你一起你轻松刷题(C++)
:fire: Leetcode :fire: 实践使完美 :party_popper: 开玩笑的单元测试 :sparkles: 简单的代码 :artist_palette: 可读代码 入门指南 git clone https: //github.com/tangweikun/leetcode.git cd leetcode npm ...
idea中leetcode插件Rust 中的 LeetCode 解决方案 怎么跑?...,所有解决方案代码都在leetcode::leetcode::editor::en并重用于leetcode 。 它有一个全局结构Solution ,所有解决方案条目都在其中实现。
leetcode:leetcode刷题
Leetcode:LeetCode解题代码
LeetCode:LeetCode的代码
LeetCode:LeetCode的注释
leetcode:LeetCode问题
加油站问题leetcode LeetCode LeetCode-JS分类列表: :smiling_face_with_smiling_eyes: :flushed_face: :winking_face: :face_with_tongue: :face_with_open_mouth: :beaming_face_with_smiling_...
leetcode:LeetCode题解