图论(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;
}
}