当前位置：首页 > news >正文

【每天学习一点算法 2026/05/15】被围绕的区域

news 2026/5/16 2:25:03

每天学习一点算法 2026/05/15

题目：被围绕的区域

给你一个 m x n 的矩阵 board ，由若干字符 ‘X’ 和 ‘O’ 组成，捕获所有被围绕的区域：
连接：一个单元格与水平或垂直方向上相邻的单元格连接。
区域：连接所有 ‘O’ 的单元格来形成一个区域。
围绕：如果一个区域中的所有 ‘O’ 单元格都不在棋盘的边缘，则该区域被包围。这样的区域完全被 ‘X’ 单元格包围。
通过原地将输入矩阵中的所有 ‘O’ 替换为 ‘X’ 来捕获被围绕的区域。你不需要返回任何值。

这道题的思路还是很简单的，首先遍历矩阵，遇到 ‘O’ 时，开始递归遍历完所有相邻的 ‘O’，如果过程没有碰到边界就将这些 ‘O’ 替换成 ‘X’，否则就不做操作。

functionsolve(board:string[][]):void{constvisited=newSet<string>();// 存储访问过的位置constoset=newSet<string>();// 存储当前遍历相邻 'O' 的位置letisBorder=false;// 是否被围绕的标识// DFS辅助函数constdfs=(row:number,col:number)=>{constkey=`${row},${col}`;// 当前元素位置信息if(visited.has(key))return;// 避免重复访问元素// 添加位置信息visited.add(key);oset.add(key);// 边界判断：触达边界则标记if(row===0||row===board.length-1||col===0||col===board[0].length-1){isBorder=true;}// 上下左右递归constdirs=[[-1,0],[1,0],[0,-1],[0,1]];for(const[dr,dc]ofdirs){constr=row+dr;constc=col+dc;if(board[r]?.[c]==='O')dfs(r,c);}};// 主遍历for(leti=0;i<board.length;i++){for(letj=0;j<board[0].length;j++){if(board[i][j]==='X'||visited.has(`${i},${j}`))continue;isBorder=false;oset.clear();dfs(i,j);// 非边界连通区域全部改为Xif(!isBorder){oset.forEach(loc=>{const[r,c]=loc.split(',').map(Number);board[r][c]='X';});}}}}

我们其实可以很容易的发现，所有 ‘O’ 相连的区域，只有两种情况：触碰到边界和未触碰到边界（被 ‘X’ 包围），那我们完全可以先找到边界上的 ‘O’，递归出他们相邻的 ‘O’，并将他们修改成另外的标识，比如 ‘C’，最终再遍历整个 board 将 ‘C’ 设成 ‘O’, ‘O’ 设成 ‘X’ 即可。

functionsolve(board:string[][]):void{// DFS辅助函数constdfs=(row:number,col:number)=>{// 将所有边界相邻的 'O' 标记为 'C'board[row][col]='C'// 上下左右递归相邻的 'O'constdirs=[[-1,0],[1,0],[0,-1],[0,1]];for(const[dr,dc]ofdirs){constr=row+dr;constc=col+dc;if(board[r]?.[c]==='O')dfs(r,c);}};for(leti=0;i<board.length;i++){// 找到左右边界上的 'O' 进行递归标记if(board[i][0]==='O')dfs(i,0)if(board[i][board[0].length-1]==='O')dfs(i,board[0].length-1)}for(leti=0;i<board[0].length;i++){// 找到上下边界上的 'O' 进行递归标记if(board[0][i]==='O')dfs(0,i)if(board[board.length-1][i]==='O')dfs(board.length-1,i)}// 遍历整个 board, 'O' --> 'X', 'C' --> 'O'for(leti=0;i<board.length;i++){for(letj=0;j<board[0].length;j++){if(board[i][j]==='O')board[i][j]='X'if(board[i][j]==='C')board[i][j]='O'}}}