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

找到所有被 ‘X’ 圍繞的區(qū)域，并將這些區(qū)域里所有的 ‘O’ 用 ‘X’ 填充。

示例:

X X X X
X O O X
X X O X
X O X X
運(yùn)行你的函數(shù)后，矩陣變?yōu)?#xff1a;

X X X X
X X X X
X X X X
X O X X
解釋:

被圍繞的區(qū)間不會(huì)存在于邊界上，換句話說，任何邊界上的 ‘O’ 都不會(huì)被填充為 ‘X’。 任何不在邊界上，或不與邊界上的 ‘O’ 相連的 ‘O’ 最終都會(huì)被填充為 ‘X’。如果兩個(gè)元素在水平或垂直方向相鄰，則稱它們是“相連”的。

代碼

class Solution {public void solve(char[][] board) {if(board.length==0) return;int n=board.length,m=board[0].length;int[][] dir=new int[][]{{0,1},{1,0},{-1,0},{0,-1}};boolean[][] check=new boolean[n][m];Queue<int[]> queue=new LinkedList<>();for(int i=0;i<m;i++)//將邊界的O入隊(duì){if(board[0][i]=='O') {queue.add(new int[]{0,i});check[0][i]=true;}if(board[n-1][i]=='O') {queue.add(new int[]{n-1,i});check[n-1][i]=true; }}for(int i=1;i<n-1;i++){if(board[i][0]=='O') {queue.add(new int[]{i,0});check[i][0]=true;}if(board[i][m-1]=='O'){queue.add(new int[]{i,m-1});check[i][m-1]=true;}}while (!queue.isEmpty())//bfs將與邊界O連接的點(diǎn)找出來標(biāo)記{int[] temp=queue.poll();for (int[] d:dir){int x=temp[0]+d[0],y=temp[1]+d[1];if(x<0||x>=n||y<0||y>=m||board[x][y]=='X'||check[x][y]) continue;queue.offer(new int[]{x,y});check[x][y]=true;}}for(int i=0;i<n;i++)//除了與邊界O連接的點(diǎn)，全部置為xfor(int j=0;j<m;j++)board[i][j]=check[i][j]?'O':'X';} }

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。