被围绕的区域
被围绕的区域
WindrunnerMax
发布于 2020-08-27 16:42:04
发布于 2020-08-27 16:42:04
被围绕的区域
给定一个二维的矩阵，包含X和O。
找到所有被X围绕的区域，并将这些区域里所有的O用X填充。
被围绕的区间不会存在于边界上，换句话说，任何边界上的O都不会被填充为X。任何不在边界上，或不与边界上的O相连的O最终都会被填充为X。如果两个元素在水平或垂直方向相邻，则称它们是相连的。
示例
X X X X
X O O X
X X O X
X O X X运行你的函数后，矩阵变为：
X X X X
X X X X
X X X X
X O X X解释
被围绕的区间不会存在于边界上，换句话说，任何边界上的O都不会被填充为X。任何不在边界上，或不与边界上的O相连的O最终都会被填充为X。如果两个元素在水平或垂直方向相邻，则称它们是相连的。
题解
/**
* @param {character[][]} board
* @return {void} Do not return anything, modify board in-place instead.
*/
var solve = function(board) {
var m = board.length;
if(m === 0) return void 0;
var n = board[0].length;
var dfs = function(x, y){
if(x<0 || y<0 || x>=m || y>=n || board[x][y] !== 'O') return void 0;
board[x][y] = 'A';
dfs(x + 1, y);
dfs(x - 1, y);
dfs(x, y + 1);
dfs(x, y - 1);
}
for (let i = 0; i < m; i++) {
dfs(i, 0);
dfs(i, n - 1);
}
for (let i = 1; i < n - 1; i++) {
dfs(0, i);
dfs(m - 1, i);
}
for (let i = 0; i < m; i++) {
for (let k = 0; k < n; k++) {
if (board[i][k] == 'A') board[i][k] = 'O';
else if (board[i][k] == 'O') board[i][k] = 'X';
}
}
return void 0;
};思路
注意到题目的解释，任何边界上的O都不会被填充为X，这句话的意思是，所有最终与边界处相连的O都不会被填充为X，注意此处的相连指的是如果两个元素在水平或垂直方向相邻，则称它们是相连的。根据解释，我们将所有边界上的O找到，然后进行深度递归，搜索所有和这个O相连的O，然后将这个O替换成其他字符，此处替换成了A，然后将矩阵中所有现在存在的O替换成X，即被包围的需要替换的O，然后将所有的A替换回O即可。首先获取矩阵的行数为m列数为n，然后定义dfs函数进行递归深度遍历，如果传递的下边不合法或者值不为O就返回，否则就将该值定义为A，然后对四个方向进行深度搜索，同样标记相连O为A，接下来对于矩阵的四个边界进行递归深度搜索，将所有与边界O相连的O标记为A，最后遍历矩阵，将矩阵中所有现在存在的O替换成X，即被包围的需要替换的O，然后将所有的A替换回O即可。
每日一题
https://github.com/WindrunnerMax/EveryDay参考
https://leetcode-cn.com/problems/surrounded-regions/本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-08-11 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录