代码随想录Day53|102.沉没孤岛 、103.水流问题 、104.建造最大岛屿

102.沉没孤岛  

import java.util.*;class Main{public static int[][] dir = {{0,1},{1,0},{0,-1},{-1,0}};public static void main (String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();int[][] grid = new int[n][m];for(int i = 0; i <n; i++){for(int j = 0; j<m; j++){grid[i][j] = sc.nextInt();}}boolean[][] visited = new boolean[n][m];for(int i = 0; i < n; i++){if(grid[i][0] == 1 && visited[i][0] == false){dfs(grid,visited,i,0);}if(grid[i][m-1] == 1 && visited[i][m-1] == false){dfs(grid,visited,i,m-1);}}//遍历上下边界for(int j = 0; j <= m-1; j++){if(grid[0][j] == 1 && visited[0][j] == false){dfs(grid,visited,0,j);}if(grid[n-1][j] == 1 && visited[n-1][j] == false){dfs(grid,visited,n-1,j);}}for(int i = 0; i < n; i++){for(int j = 0; j< m; j++){if(grid[i][j] == 1) grid[i][j] = 0;if(grid[i][j] == 2) grid[i][j] = 1;}}for(int i = 0; i < n; i++ ){for(int j = 0; j< m; j++){System.out.print(grid[i][j]+" ");}System.out.println();}}public static void dfs(int[][] grid, boolean[][] visited, int x,int y){if(visited[x][y] == true || grid[x][y] == 0){return;}grid[x][y] = 2;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 || nextY >= grid[0].length || nextX < 0 || nextX >= grid.length){continue;}dfs(grid,visited,nextX,nextY);}}
}

103.水流问题 

import java.util.*;class Main{public static int[][] dir = {{1,0},{0,1},{-1,0},{0,-1}};public static void main (String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();int[][] grid = new int[n][m];for(int i = 0; i < n; i++){for(int j = 0; j< m; j++){grid[i][j] = sc.nextInt();}}//初始化边界boolean[][] firstBound = new boolean[n][m],secondBound = new boolean[n][m];//遍历左边界和有边界for(int i = 0; i < n; i++){dfs(grid,i,0,firstBound);dfs(grid,i,m-1,secondBound);}//遍历上边界和下边界for(int i = 0; i <m; i++){dfs(grid,0,i,firstBound);dfs(grid,n-1,i,secondBound);}for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){if(firstBound[i][j] && secondBound[i][j]){System.out.println(i+" " + j);}}}}public static void dfs(int[][] grid,int x,int y,boolean[][] visited){//不能放在遍历里面，否则刚进来第一组没办法变成truevisited[x][y] = true;for(int i = 0; i < 4; i++){int nextX= x + dir[i][0];int nextY = y + dir[i][1];if( nextX <0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length || grid[nextX][nextY] < grid[x][y] ||visited[nextX][nextY]){continue;}dfs(grid,nextX,nextY,visited);}}
}

104.建造最大岛屿

import java.util.*;class Main{public static int[][] dirs = {{1,0},{0,1},{-1,0},{0,-1}};static int count = 0;static int tag = 2;public static void main (String[] args) {/* code */Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();int[][] grid = new int[n][m];boolean[][] visited = new boolean[n][m];for(int i = 0; i< n; i++){for(int j = 0; j< m; j++){grid[i][j] = sc.nextInt();}}boolean totalIsland = true;//遍历记录面积Map<Integer,Integer> countArea = new HashMap<>();for(int i = 0; i<n; i++){for(int j = 0; j< m; j++){if(grid[i][j] == 0) totalIsland = false;if( !visited[i][j] && grid[i][j] != 0){count = 0;dfs(grid,visited,i,j);countArea.put(tag++,count);}}}/*/打印数组for(int i = 0; i< n; i++){for(int j = 0; j< m; j++){System.out.print(grid[i][j] + " ");}System.out.println();}//*/int res = 1;HashSet<Integer> island = new HashSet<>();int flag = 0;//再次遍历添加小岛for(int i = 0; i<n; i++){for(int j = 0; j< m; j++){if(grid[i][j] == 0){int area = 1;island.clear();for(int dir[]:dirs){int nextX = i + dir[0];int nextY = j + dir[1];if(nextX < 0 || nextX >= grid.length || nextY < 0|| nextY >= grid[0].length) continue;flag =grid[nextX][nextY];if(!island.contains(flag) && countArea.containsKey(flag)){area+=countArea.get(flag);island.add(flag);}}res = Math.max(area,res);}}}if(totalIsland == false){System.out.println(res);}else{System.out.println(m*n);}}public static void dfs(int[][] grid, boolean[][] visited, int x, int y){visited[x][y] = true;grid[x][y] = tag;count++;for(int[] dir: dirs){int nextX = x + dir[0];int nextY = y + dir[1];if(nextX < 0 || nextX >= grid.length || nextY < 0|| nextY >= grid[0].length || visited[nextX][nextY] || grid[nextX][nextY] == 0){continue;}dfs(grid, visited, nextX, nextY);}}
}