leetcode 200 岛屿问题文章来源:https://www.toymoban.com/news/detail-700653.html
class Solution {
//定义对应的方向
boolean [][] visited;
int dir[][]={
{0,1},{1,0},{-1,0},{0,-1}
};
public int numIslands(char[][] grid) {
//对应的二维数组
int count=0;
visited=new boolean[grid.length][grid[0].length];
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (visited[i][j] == false && grid[i][j]=='1') {
count++;
dfs(grid,i,j);
}
}
}
return count;
}
public void dfs(char[][]grid,int x,int y)
{
if (visited[x][y]==true||grid[x][y]=='0'){
return;
}
visited[x][y]=true;
for (int i = 0; i <4; i++) {
int nextX=x+dir[i][0];
int nextY=y+dir[i][1];
if (nextY<0||nextX<0||nextX>=grid.length||nextY>=grid[0].length){
continue;
}
dfs(grid,nextX,nextY);
}
}
}
BFS代码文章来源地址https://www.toymoban.com/news/detail-700653.html
class Solution{
boolean[][] visited;
int move[][]={
{0,1},{0,-1},{1,0},{-1,0}};
public int numIslands(char[][] grid) {
int res=0;
visited=new boolean[grid.length][grid[0].length];
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (!visited[i][j]&&grid[i][j]=='1'){
bfs(grid,i,j);
res++;
}
}
}
return res;
}
public void bfs(char [][] grid,int x,int y){
Deque<int[]> queue=new ArrayDeque<>(); //创建一个队列
queue.offer(new int[]{x,y});
visited[x][y]=true;
while (!queue.isEmpty()){
int []cur=queue.poll();
int m=cur[0];
int n=cur[1];
for (int i=0;i<4;i++){
int nextx=m+move[i][0];
int nexty=n+move[i][1];
if (nextx<0||nextx==grid.length||nexty<0||nexty==grid[0].length){
continue;
}
if (!visited[nextx][nexty]&&grid[nextx][nexty]=='1'){
queue.offer(new int[]{nextx,nexty});
visited[nextx][nexty]=true;
}
}
}
}
到了这里,关于图论岛屿问题DFS+BFS的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!