图论岛屿问题DFS+BFS

leetcode 200 岛屿问题

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代码

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;}}}}