Leetcode130:SurroundedRegions

Leetcode130:SurroundedRegions
这题就是基本的DFS/BFS加入一些变形,用DFS/BFS都可以解。我两种方法都写了一下,DFS要简洁一些。
DFS:

public class Solution {

int m,n;

char[][]board;

void dfs(int x,int y){

if(x<0 ||x>=m || y<0 || y>=n ||board[x][y]!='O') return;

board[x][y]='D';

dfs(x-1,y);

dfs(x+1,y);

dfs(x,y-1);

dfs(x,y+1);

}

public voidsolve(char[][] board){

if(board==null ||board.length==0) return;

this.board=board;

m=board.length;

n=board[0].length;

for(intj=0;j<n;j++){

dfs(0,j);

dfs(m-1,j);

}

for(inti=1;i<m-1;i++){

dfs(i,0);

dfs(i,n-1);

}

for(inti=0;i<m;i++)

for(int j=0;j<n;j++){

if(board[i][j]=='O') board[i][j]='X';

elseif(board[i][j]=='D') board[i][j]='O';

}

}

}


BFS:public class Solution { int m,n; char[][] board; Queue<Integer> queue=newLinkedList<Integer>(); void fill(int x, inty){ if(x<0 || x>=m ||y<0 || y>=n || board[x][y]!='O')return; queue.offer(x*m+y); board[x][y]='D'; } void bfs(int x, inty){ fill(x,y); while(!queue.isEmpty()){ intcurr=queue.poll(); inti=curr/n; intj=curr%n; fill(i-1,j); fill(i+1,j); fill(i,j-1); fill(i,j+1); } } public voidsolve(char[][] board){ if(board==null || board.length==0) return; this.board=board; m=board.length; n=board[0].length; for(int j=0;j<n;j++){ bfs(0,j); bfs(m-1,j); } for(int i=1;i<m-1;i++){ bfs(i,0); bfs(i,n-1); } for(int i=0;i<m;i++) for(intj=0;j<n;j++){ if(board[i][j]=='O')board[i][j]='X'; else if(board[i][j]=='D')board[i][j]='O'; } }}
博主对本博客文章及代码享有著作权。网络转载请注明出处http://blog.sina.com.cn/leetcode。整理出版物请和作者联系。

  

爱华网本文地址 » http://www.aihuau.com/a/25101013/172782.html

更多阅读

电影《大人物》 张越开口供出大人物

在剧组这段时间一晃就过去了,很辛苦,但是很精彩。在自己的老家工作,倍感亲切,喝的水格外甜。吃得饭,格外香。《大人物》是我国首部励志喜剧,在大家的欢声笑语中又渗透着感动,布满了奋斗的痕迹,之所会接这部剧,是因为被剧中的人物所感动,不仅

威海海参 威海海参-产地环境,威海海参-品质特点

威海海参,山东省威海市沿海特产,中国地理标志产品。威海的海参属于刺参,刺参产业一直是威海海产品生产加工的优势产业。威海沿海岩礁众多,海藻茂密,海底腐植碎屑丰富,因此所产海参个体肥大,突棘粗大,肉质肥厚,鲜嫩可口。“威海野生刺参”获农

自然灾害概述 自然 自然-一般解释,自然-概述

自然,来自拉丁文Natura,意指“天地万物之道”,原意为植物、动物及其它世界面貌自身发展出来的内在特色,最早的文献中意义为植物。最广义来说可以是自然界、物理学宇宙、物质世界或物质宇宙。现在有天然、自然界现象、人的自然本性和自然

声明:《Leetcode130:SurroundedRegions》为网友青丝缠梳分享!如侵犯到您的合法权益请联系我们删除