原創公眾號：bigsai 歡迎加入力扣打卡
文章已收錄在 全網都在關注的數據結構與算法學習倉庫 歡迎star

題目描述

給定一個二維的矩陣，包含 ‘X’ 和 ‘O’（字母 O）。

找到所有被 ‘X’ 圍繞的區域，并將這些區域里所有的 ‘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’。如果兩個元素在水平或垂直方向相鄰，則稱它們是“相連”的。

分析

對于題意是很容易理解的，也就是只有和邊緣連接的O不會被 X 包圍，其他都會被X包圍。

這是一道圖論搜索題，核心的處理思路就是找矩陣所有邊緣開始，如果是x那么跳過，如果是o那么開始查找與該點上下左右聯通的點進行標記(被標記則證明沒有被包圍)。那么最終剩下沒有被標記的節點就是保留o。其他節點全部變成x.

在具體處理上dfs或者bfs都可以，向四周遍歷時候記得不能出界。

具體代碼：

class Solution {int X[]={0,1,0,-1};int Y[]={1,0,-1,0};public void solve(char[][] board) {int lenx=board.length,leny=board[0].length;boolean jud[][]=new boolean[lenx][leny];for(int i=0;i<lenx;i++)//兩個豎得{if(board[i][0]=='O'&&!jud[i][0]){judgle(i,0,board,jud);jud[i][0]=true;}if(board[i][leny-1]=='O'&&!jud[i][leny-1]){judgle(i,leny-1,board,jud);jud[i][leny-1]=true;}}for(int i=0;i<leny;i++)//兩個橫得{if(board[0][i]=='O'&&!jud[0][i]){judgle(0,i,board,jud);jud[0][i]=true;}if(board[lenx-1][i]=='O'&&!jud[lenx-1][i]){judgle(lenx-1,i,board,jud);jud[lenx-1][i]=true;}}for(int i=0;i<lenx;i++){for(int j=0;j<leny;j++){if(!jud[i][j]){board[i][j]='X'; }}}}private void judgle(int x, int y, char[][] board, boolean[][] jud) {// TODO Auto-generated method stubfor(int i=0;i<4;i++){int x1=x+X[i];int y1=y+Y[i];if(x1>=0&&x1<board.length&&y1>=0&&y1<board[0].length){if(!jud[x1][y1]&&board[x1][y1]=='O'){jud[x1][y1]=true;judgle(x1, y1, board, jud);}}} } }

咱們下次再見！關注后歡迎加入力扣打卡群(備注力扣 csdn即可)。

總結

以上是生活随笔為你收集整理的被围绕的区域(dfs)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。