1. 卡码网101. 孤岛的总面积
题目链接：https://kamacoder.com/problempage.php?pid=1173
文章链接：https://www.programmercarl.com/kamacoder/0101.孤岛的总面积.html#思路
思路：
找到岛屿，检查是否是孤岛，统计面积
解法：
import java.util.*;public class Main {static int[][] dir = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};static boolean isLone = true;//是否是孤岛static int area = 0;static int sumArea = 0;public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();// 行int m = sc.nextInt();// 列int[][] matrix = new int[n][m];boolean[][] invited = new boolean[n][m];for (int i=0;i<n;i++) {for (int j=0;j<m;j++) {matrix[i][j] = sc.nextInt();}}for (int i=0;i<n;i++) {for (int j=0;j<m;j++) {// 找到新的岛屿if (!invited[i][j] && matrix[i][j]==1) {// 遍历所有陆地//dfs(matrix,invited,i,j);bfs(matrix,invited,i,j);if (isLone) {sumArea += area;}area = 0;isLone = true;} }}System.out.println(sumArea);}// dfspublic static void dfs (int[][] matrix,boolean[][] invited,int x,int y) {//检查是否是已被访问陆地或者海洋if (invited[x][y] || matrix[x][y]!=1) {return;}// 检查是否是孤岛if (x==0||x==matrix.length-1||y==0||y==matrix[0].length-1) {isLone=false;//不是孤岛}//登陆访问invited[x][y] = true;area++;for (int i=0;i<4;i++) {int ptx = x + dir[i][0];int pty = y + dir[i][1];// 检查是否越界if (ptx<0||ptx>=matrix.length||pty<0||pty>=matrix[0].length) {continue;}// 递归dfs(matrix,invited,ptx,pty);}}//bfspublic static void bfs (int[][] matrix,boolean[][] invited,int x,int y) {Deque<int[]> deque = new ArrayDeque<>();// 检查是否是孤岛if (x==0||x==matrix.length-1||y==0||y==matrix[0].length-1) {isLone=false;//不是孤岛}// 添加到队列中deque.offer(new int[]{x,y});invited[x][y] = true;area++;while (!deque.isEmpty()) {int ptx = deque.peek()[0];int pty = deque.peek()[1];deque.poll(); //出队for (int i=0;i<4;i++) {int nextx = ptx + dir[i][0];int nexty = pty + dir[i][1];// 检查是否越界if (nextx<0||nextx>=matrix.length||nexty<0||nexty>=matrix[0].length) {continue;}//检查是否是未被访问的陆地if (!invited[nextx][nexty]&&matrix[nextx][nexty]==1) {// 检查是否是孤岛if (nextx==0||nextx==matrix.length-1||nexty==0||nexty==matrix[0].length-1) {isLone=false;//不是孤岛}deque.offer(new int[]{nextx,nexty});invited[nextx][nexty]=true;area++;}}}}}
2.卡码网 102. 沉没孤岛
题目链接：https://kamacoder.com/problempage.php?pid=1174
文章链接：https://www.programmercarl.com/kamacoder/0102.沉没孤岛.html#其他语言版本
思路：
找到岛屿，检查是否是孤岛，然后将孤岛中的陆地设为0
import java.util.*;public class Main {static int[][] dir = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};static boolean notLone = false;public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();// 行int m = sc.nextInt();// 列int[][] matrix = new int[n][m];boolean[][] visted = new boolean[n][m];// 是否被访问for (int i=0;i<n;i++) {for (int j=0;j<m;j++) {matrix[i][j] = sc.nextInt();}}for (int i=0;i<n;i++) {for (int j=0;j<m;j++) {// 检查是否是未被访问的陆地if (!visted[i][j] && matrix[i][j]==1) {Deque<int[]> loneDeque = new ArrayDeque<>();// dfs(matrix,visted,i,j,loneDeque);bfs(matrix,visted,i,j,loneDeque);if (!notLone) {while (!loneDeque.isEmpty()) {int ptx = loneDeque.peek()[0];int pty = loneDeque.peek()[1];loneDeque.poll();matrix[ptx][pty]=0;}}notLone = false;}}}for (int[] pa : matrix) {for (int i = 0; i < pa.length - 1; i++) {System.out.print(pa[i] + " ");}System.out.println(pa[pa.length - 1]);}}// dfspublic static void dfs(int[][] matrix,boolean[][] visted,int x,int y,Deque<int[]> loneDeque) {// 检查是否是被访问的陆地或者海洋if (visted[x][y] || matrix[x][y]==0) {return;}// 检查是否是孤岛if (x==0||x==matrix.length-1||y==0||y==matrix[0].length-1) {notLone=true;// 不是孤岛}visted[x][y]=true;loneDeque.offer(new int[]{x,y});for (int i=0;i<4;i++) {int ptx = x+dir[i][0];int pty = y+dir[i][1];// 检查是否越界if (ptx<0||ptx>=matrix.length||pty<0||pty>=matrix[0].length) {continue;}dfs(matrix,visted,ptx,pty,loneDeque);}}//bfspublic static void bfs(int[][] matrix,boolean[][] visted,int x,int y,Deque<int[]> loneDeque) {Deque<int[]> deque = new ArrayDeque<>();// 检查是否是孤岛if (x==0||x==matrix.length-1||y==0||y==matrix[0].length-1) {notLone=true;// 不是孤岛}deque.offer(new int[]{x,y});loneDeque.offer(new int[]{x,y});visted[x][y]=true;while (!deque.isEmpty()) {int ptx = deque.peek()[0];int pty = deque.peek()[1];deque.poll();for (int i=0;i<4;i++) {int nextx = ptx + dir[i][0];int nexty = pty + dir[i][1];//检查是否越界if (nextx<0||nextx>=matrix.length||nexty<0||nexty>=matrix[0].length) {continue;}// 检查是否是未被访问的陆地if (!visted[nextx][nexty]&&matrix[nextx][nexty]==1) {// 检查是否是孤岛if (nextx==0||nextx==matrix.length-1||nexty==0||nexty==matrix[0].length-1) {notLone=true;// 不是孤岛}deque.offer(new int[]{nextx,nexty});loneDeque.offer(new int[]{nextx,nexty});visted[nextx][nexty]=true;}}}}}
3. 卡码网 103. 水流问题
题目链接：https://kamacoder.com/problempage.php?pid=1175
文章链接：https://www.programmercarl.com/kamacoder/0103.水流问题.html#优化
思路：
两种思路：
1.遍历每个点，然后看这个点 能不能同时到达第一组边界和第二组边界。即，由高向低遍历。
至于遍历方式，可以用dfs，也可以用bfs。最终会导致代码超时。
2. 从第一组边界上的节点 逆流而上，将遍历过的节点都标记上。同样从第二组边界的边上节点 逆流而上，将遍历过的节点也标记上。即，从边界出发，由低向高遍历。
然后两方都标记过的节点就是既可以流向第一组边界也可以流向第二组边界的节点。
从第一组边界边上节点出发，如图：
从第二组边界上节点出发，如图：
import java.util.*;public class Main {public static int[][] dir = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};public static void main (String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();// 行int m = sc.nextInt();// 列int[][] matrix = new int[n][m];for (int i=0;i<n;i++) {for (int j=0;j<m;j++) {matrix[i][j] = sc.nextInt();}}boolean[][] firstBroad = new boolean[n][m];boolean[][] secondBroad = new boolean[n][m];//从左边界和右边界出发for (int i=0;i<n;i++) {// dfs(matrix,firstBroad,i,0);// dfs(matrix,secondBroad,i,m-1);bfs(matrix,firstBroad,i,0);bfs(matrix,secondBroad,i,m-1);}//从上边界和下边界出发for (int j=0;j<m;j++) {// dfs(matrix,firstBroad,0,j);// dfs(matrix,secondBroad,n-1,j);bfs(matrix,firstBroad,0,j);bfs(matrix,secondBroad,n-1,j);}for (int i=0;i<n;i++) {for (int j=0;j<m;j++) {if (firstBroad[i][j]&&secondBroad[i][j]) {System.out.println(i+" "+j);}}}}//dfspublic static void dfs (int[][] matrix,boolean[][] visted,int x,int y) {// 检查是否访问过if (visted[x][y]) {return;}visted[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>=matrix.length||nexty<0||nexty>=matrix[0].length) {continue;}// 检查(nextx,nexty)的高度是否小于(x,y)的高度if (matrix[x][y]>matrix[nextx][nexty]) {continue;}dfs(matrix,visted,nextx,nexty);}}//bfspublic static void bfs(int[][] matrix,boolean[][] visted,int x,int y) {Deque<int[]> deque = new ArrayDeque<>();if (visted[x][y]) {return;}deque.offer(new int[]{x,y});visted[x][y]=true;while (!deque.isEmpty()) {int ptx = deque.peek()[0];int pty = deque.peek()[1];deque.poll();for (int i=0;i<4;i++) {int nextx = ptx+dir[i][0];int nexty = pty+dir[i][1];// 检查是否越界if (nextx<0||nextx>=matrix.length||nexty<0||nexty>=matrix[0].length) {continue;}if (visted[nextx][nexty]) {continue;}// 检查(nextx,nexty)的高度是否小于(ptx,pty)的高度if (matrix[ptx][pty]>matrix[nextx][nexty]) {continue;}deque.offer(new int[]{nextx,nexty});visted[nextx][nexty]=true;}}}
}
4.卡码网 104.建造最大岛屿
题目链接：https://kamacoder.com/problempage.php?pid=1176
文章链接：https://www.programmercarl.com/kamacoder/0104.建造最大岛屿.html#思路
思路：
用一次深搜把每个岛屿的面积记录下来。
第一步：一次遍历地图，得出各个岛屿的面积，并做编号记录。可以使用map记录，key为岛屿编号，value为岛屿面积
第二步：再遍历地图，遍历0的方格（因为要将0变成1），并统计该1（由0变成的1）周边岛屿面积，将其相邻面积相加在一起，遍历所有 0 之后，就可以得出 选一个0变成1 之后的最大面积。
import java.util.*;public class Main {static int area=0;static int[][] dir = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};static boolean isAllGrid = true; // 标记是否整个地图都是陆地public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();// 行int m = sc.nextInt();// 列int[][] matrix = new int[n][m];boolean[][] visted = new boolean[n][m];for (int i=0;i<n;i++) {for (int j=0;j<m;j++) {matrix[i][j] = sc.nextInt();}}Map<Integer,Integer> areaMap = new HashMap<>();int mark=2;for (int i=0;i<n;i++) {for (int j=0;j<m;j++) {// 检查是否是海洋if (matrix[i][j]==0) {isAllGrid=false;}// 检查是否是未被访问的陆地if (!visted[i][j] && matrix[i][j]==1) {area=0;// 收集各个岛屿的面积并标记dfs(matrix,visted,i,j,mark);areaMap.put(mark,area);mark++;}}}int resultArea=0;if (isAllGrid) {resultArea = n*m;}for (int i=0;i<n;i++) {for (int j=0;j<m;j++) {if (matrix[i][j]==0) {int areaS = 1;Set<Integer> set = new HashSet<>();// 对海洋的四个方向分析for (int d=0;d<4;d++) {int ptx=i+dir[d][0];int pty=j+dir[d][1];// 检查是否越界if (ptx<0||ptx>=matrix.length||pty<0||pty>=matrix[0].length) {continue;}int curMark = matrix[ptx][pty];// 检查是否是海洋if(curMark==0) {continue;}// 检查是否已经包含了该岛屿if (set.contains(curMark)) {continue;}set.add(curMark);areaS = areaS + areaMap.get(curMark);}resultArea = Math.max(resultArea,areaS);}}}System.out.println(resultArea);}public static void dfs(int[][] matrix,boolean[][] visted,int x,int y,int mark) {// 检查是否是已被访问或者是海洋if (visted[x][y]||matrix[x][y]==0){return;}visted[x][y]=true;matrix[x][y]=mark;area++;for (int i=0;i<4;i++) {int nextx = x+dir[i][0];int nexty = y+dir[i][1];// 检查是否越界if (nextx<0||nextx>=matrix.length||nexty<0||nexty>=matrix[0].length) {continue;}dfs(matrix,visted,nextx,nexty,mark);}}
}