图论(dfs系列) 9/27

一、二维网格图中探测环

题意:

给定一个二维数组grid,如果二维数组中存在一个环，处于环上的值都是相同的。返回true；如果不存在就返回false；

思路：

在以往的dfs搜索中，都是往四个方向去dfs；但是在这一道题中，四个方向是不行的；如果第i次是从左往右过来的，那么i+1次，就不能从右往左再过

去。所以应该加上这个判断。

那我们就要走dfs函数上多加一个参数，from。

如果上一次不是从左边来的，那我们就可以往左走；

如果上一次不是从右边来的，那我们就可以往右走；

以此类推

    public void dfs(int x, int y, char ch, char from) {if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] != ch) {return;}if (visited[x][y]) {hasRing = true;return;}visited[x][y] = true;if (from != 'L')dfs(x, y - 1, ch, 'R');if (from != 'R')dfs(x, y + 1, ch, 'L');if (from != 'U')dfs(x-1, y, ch, 'D');if (from != 'D')dfs(x+1, y, ch, 'U');}

代码：

class Solution {boolean[][] visited;char[][] grid;int m, n;boolean hasRing;public boolean containsCycle(char[][] grid) {m = grid.length;n = grid[0].length;visited = new boolean[m][n];this.grid = grid;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (!visited[i][j]) {dfs(i, j, grid[i][j], 'L');if (hasRing) return true;}}}return false;}public void dfs(int x, int y, char ch, char from) {if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] != ch) {return;}if (visited[x][y]) {hasRing = true;return;}visited[x][y] = true;if (from != 'L')dfs(x, y - 1, ch, 'R');if (from != 'R')dfs(x, y + 1, ch, 'L');if (from != 'U')dfs(x-1, y, ch, 'D');if (from != 'D')dfs(x+1, y, ch, 'U');}
}

二、最大人工岛

思路:

1.首先找到所有的岛屿(连通块)，将他们存储到map表中。可以使用一个值来标识一个连通块。

        Map<Integer,Integer> map=new HashMap<>();for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(grid[i][j]==1){int area=dfs(grid,i,j,islandIdx);//计算每一个连通块的大小map.put(islandIdx,area);//然后放到map里面保存islandIdx++;//maxArea=Math.max(area,maxArea);}}}

2.将所有的连通块找出来之后，然后枚举所有的海洋块。判断海洋块的周围有没有两个连通块(最多只能有两个连通块)。在枚举的同时，比较得出最大面积值。

        //枚举所有0的上下左右可能连接的情况for(int i=0;i<n;i++){for(int j=0;j<n;j++){Set<Integer> set=new HashSet<>();if(grid[i][j]==0){//左边的格子 如果是岛屿 就把岛屿编号放进来if(i-1>=0&&grid[i-1][j]>=2){set.add(grid[i-1][j]);}if(i+1<n&&grid[i+1][j]>=2){set.add(grid[i+1][j]);}if(j-1>=0&&grid[i][j-1]>=2){set.add(grid[i][j-1]);}if(j+1<n&&grid[i][j+1]>=2){set.add(grid[i][j+1]);}int curMaxArea=1;for(Integer index:set){int otherArea=map.get(index);curMaxArea+=otherArea;}maxArea=Math.max(maxArea,curMaxArea);}}}

代码：

class Solution {int n;public int largestIsland(int[][] grid) {n=grid.length;int maxArea=0,islandIdx=2;//对所有岛屿编号并记录在哈希表中Map<Integer,Integer> map=new HashMap<>();for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(grid[i][j]==1){int area=dfs(grid,i,j,islandIdx);//计算每一个连通块的大小map.put(islandIdx,area);//然后放到map里面保存islandIdx++;//maxArea=Math.max(area,maxArea);}}}//枚举所有0的上下左右可能连接的情况for(int i=0;i<n;i++){for(int j=0;j<n;j++){Set<Integer> set=new HashSet<>();if(grid[i][j]==0){//左边的格子 如果是岛屿 就把岛屿编号放进来if(i-1>=0&&grid[i-1][j]>=2){set.add(grid[i-1][j]);}if(i+1<n&&grid[i+1][j]>=2){set.add(grid[i+1][j]);}if(j-1>=0&&grid[i][j-1]>=2){set.add(grid[i][j-1]);}if(j+1<n&&grid[i][j+1]>=2){set.add(grid[i][j+1]);}int curMaxArea=1;for(Integer index:set){int otherArea=map.get(index);curMaxArea+=otherArea;}maxArea=Math.max(maxArea,curMaxArea);}}}return maxArea;       }public int dfs(int[][] grid,int x,int y,int count){if(!isArea(grid,x,y)||grid[x][y]==count||grid[x][y]!=1)return 0;grid[x][y]=count;return 1+dfs(grid,x-1,y,count)+dfs(grid,x+1,y,count)+dfs(grid,x,y-1,count)+dfs(grid,x,y+1,count);}public boolean isArea(int[][] grid, int x, int y) {if (x >= n || x < 0 || y < 0 || y >= n)return false;return true;}
}