给定一个m行n列的二维地图, 初始化每个单元都是水.
操作addLand 把单元格(row,col)变成陆地.
岛屿定义为一系列相连的被水单元包围的陆地单元, 横向或纵向相邻的陆地称为相连(斜对角不算).
在一系列addLand的操作过程中, 给出每次addLand操作后岛屿的个数.
二维地图的每条边界外侧假定都是水.
多组测试数据,请参考例题处理 每组数据k+3行, k表示addLand操作次数 第一行:表示行数m 第二行:表示列数n 第三行:表示addLand操作次数k 第4~k+3行:row col 表示addLand的坐标。注意超过边界的坐标是无效的。
一行,k个整数, 表示每次addLand操作后岛屿的个数, 用空格隔开,结尾无空格
3 3 4 0 0 0 1 1 2 2 1
1 1 2 3
import java.util.Scanner; import java.util.Set; import java.util.HashSet; import java.util.Arrays; import java.util.Iterator; public class Main{ //定义全局的方向向量,便于用循环来遍历四个方向 public static int[][] dir=new int[][]{{0,1},{1,0},{0,-1},{-1,0}}; public static void main(String[] args){ /** *1.前期准备工作 */ Scanner in=new Scanner(System.in); //获取统计参数:行数/列数/操作数 int rows=in.nextInt(); int columns=in.nextInt(); int actions=in.nextInt(); //构造一个地图的数据结构, //record[][][0]: 0为水 1为陆地 //record[][][1]: 唯一标志,标识这个陆地属于哪个岛屿,=加入岛屿的土地数量-1; int[][][] record=new int[rows+2][columns+2][2]; //超范围的容器是为了不用判断边界,把边界周围的水也表示出来 boolean[][] visited=new boolean[rows+2][columns+2]; //设置一个单增序号nextNum,每次添加一块陆地的时候,都会使得该序号增大, //可以作为地块的计数. //定义一个 int count=0; int nextNum=0; /** *2.操作循环 */ while(actions>0){ int row=in.nextInt()+1; int col=in.nextInt()+1; int waters=0; //利用其去重性,来判断一块地将要连接起来的岛屿数量,表示为set.size(); Set<Integer> set=new HashSet<Integer>(); /** *2.1 当该坐标已经访问过,或者该坐标不在地图范围,则输出当前的岛屿数量 * 同时操作循环数量自减,这俩不可省略 * 为了满足要求"结尾无空格",输出时需要判断 */ if(row>rows||col>columns||row<0||col<0|| record[row][col][0]==1){ if(actions>0){ System.out.print(count+" "); }else{ System.out.print(count); } actions--; continue; } /** *2.2 如果没有超出地图范围,并且当前是新加入的陆地,则对周围环境进行检索 *2.2.1记录新地块周围的水的边界数量,以及岛屿的数量(即record[][][1]的值的种类,同一岛屿该值相同,该值为岛屿唯一识别代码) *2.2.2判断周围水的边界数量,如果4面都是水,则岛屿计数+1,否则进入下一步; *2.2.3判断周围的 */ //如果没有超出范围,则设置当前位置为陆地,并给他唯一识别符号,同时识别符自增; record[row][col][0]=1; record[row][col][1]=nextNum++; for(int i=0;i<4;i++){ int temprec=record[row +dir[i][0]][col+dir[i][1]][0]; if(temprec==0){ waters++;//如果相邻是水,记录周围有多少的水 }else{ set.add(record[row +dir[i][0]][col+dir[i][1]][1]); //如果周围是土地,记录是属于多少个岛屿,将其代号加入其中 } } if(waters==4){ count++;//如果是4面都是水,则认为新增一个陆地,否则就是相连的 }else { count=count-set.size()+1;//否则就是加入了别的岛屿,岛屿数量更新(可能会合并) /*3. *更新连接的岛屿的全部标识代号*/ new Main().dfs(row,col,record,new boolean[rows+2][columns+2],nextNum-1);//然后把这个岛的全部位置都遍历一遍,写为新的值 } /** *输出格式控制*/ if(actions>0){ System.out.print(count+" "); }else{ System.out.print(count); } actions--;//更新当前剩余操作步数 } } /* *作用:当前土地加入到了原来的岛屿,或者连接了多个岛屿,此函数基于深度优先原理用于 *更新当前土地连接的岛屿的所有土地的唯一标识为最新加入元素的标识,一家人整整齐齐, *便于下次判断*/ public void dfs(int rows,int columns,int[][][] record,boolean[][] visited,int num){ if(visited[rows][columns]||record[rows][columns][0]==0){ return;//访问过,或者说是水,则跳过 } visited[rows][columns]=true;//开始访问,写一个访问标记 record[rows][columns][1]=num; for(int i=0;i<4;i++ ){ dfs(rows+dir[i][0],columns+dir[i][1],record,visited,num);//开始向四面八方递归 } } }
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; public class Main { private static int[] dx = new int[]{1, -1, 0, 0}; private static int[] dy = new int[]{0, 0, 1, -1}; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int m = Integer.parseInt(br.readLine().trim()), n = Integer.parseInt(br.readLine().trim()); int k = Integer.parseInt(br.readLine().trim()); int[][] grid = new int[m][n]; String[] params; for(int i = 0; i < k; i++){ params = br.readLine().trim().split(" "); int x = Integer.parseInt(params[0]); int y = Integer.parseInt(params[1]); if(x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == 1) { // 坐标不能越界且不重复造陆地 System.out.print(getIslandNums(grid) + " "); continue; } grid[x][y] = 1; System.out.print(getIslandNums(grid) + " "); } } private static int getIslandNums(int[][] map) { int m = map.length, n = map[0].length, count = 0; int[][] grid = new int[m][n]; for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++) grid[i][j] = map[i][j]; } for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ if(grid[i][j] == 1){ count ++; infect(i, j, grid); } } } return count++; } private static void infect(int i, int j, int[][] map) { if(i < 0 || i >= map.length || j < 0 || j >= map[0].length || map[i][j] == 0) return; map[i][j] = 0; infect(i + 1, j, map); infect(i - 1, j, map); infect(i, j + 1, map); infect(i, j - 1, map); } }
import java.util.*; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); while (in.hasNextInt()) { int row = in.nextInt(); int col = in.nextInt(); int[][] grid = new int[row][col]; int num = in.nextInt(); int count = 0; StringBuilder sb = new StringBuilder(); for(int i = 0; i < num; i++){ int r = in.nextInt(); int c = in.nextInt(); if(isValid(row,col,r,c)){ count = 0; grid[r][c] = 1; int[][] temp = new int[grid.length][grid[0].length]; //深拷贝 for (int k = 0; k < grid.length; k++) { temp[k] = Arrays.copyOf(grid[k], grid[k].length); } for(int a = 0; a < temp.length; a++){ for(int b = 0; b < temp[0].length; b++){ if(temp[a][b] == 1){ count++; dfs(temp,a,b); } } } } sb.append(count); sb.append(" "); } System.out.println(sb.toString().trim()); } } //将与grid[a][b]相邻的陆地都标记为海洋 public static void dfs(int[][] grid, int a, int b){ if(!isValid(grid.length, grid[0].length, a, b) || grid[a][b] == 0) return; else{ grid[a][b] = 0; dfs(grid,a - 1,b); dfs(grid,a + 1,b); dfs(grid,a,b + 1); dfs(grid,a,b - 1); } } //判断输入合法性 public static boolean isValid(int row, int col, int r, int c){ if(r < 0 || r >= row || c < 0 || c >= col) return false; return true; } }我有个疑问求大佬解答,拷贝一个不影响原值的int[][],如上面的20行,是不是必须深拷贝呀?还有什么简便写法嘛?
public class Main/*CountIslands*/ { // 4个方向 final static int[][] dir = {{1, -1, 0, 0}, {0, 0, 1, -1}}; // 将二维信息行号r、列号c根据总列数cor映射成一维 static int hashCor(int r, int c, int col) { return r*col + c + 1;// 加一是因为要将0当作水,加上1避免和0冲突 } // 并查集模板 // 如果par[x]为0,则代表该点是水 static int[] par, rank; static int find(int x) { return x==par[x] ? x : (par[x] = find(par[x])); } static void union(int x, int y) { if ((x=find(x)) == (y=find(y))) return; if (rank[x] < rank[y]) { par[x] = y; } else { par[y] = x; if (rank[x] == rank[y]) rank[x]++; } } static boolean same(int x, int y) { return find(x) == find(y); } public static void main(String[] args) { java.util.Scanner sc = new java.util.Scanner(System.in); int isNum, row, col, i, r, c, opNum, nearR, nearC; while (sc.hasNext()) { row = sc.nextInt(); col = sc.nextInt(); opNum = sc.nextInt(); isNum = 0;// 岛的个数 par = new int[row*col+1];//一开始每个点的父节点均为0,代表水 rank = new int[row*col+1]; while (opNum-- > 0) { r = sc.nextInt(); c = sc.nextInt(); // 如果行号r和列号c不越界且该点当前是水 if (r>=0 && r<row && c>=0 && c<col && find(hashCor(r,c,col))==0){ isNum++; par[hashCor(r, c, col)] = hashCor(r, c, col); for (i = 0; i < 4; ++i) {//遍历临近4个点的坐标 nearR = r+dir[0][i]; nearC = c+dir[1][i]; // 如果该点不越界且是一块陆地且和当前的这一点不属于同一个岛 if (nearR>=0 && nearR<row && nearC>=0 && nearC<col && find(hashCor(nearR, nearC, col)) != 0 && !same(hashCor(nearR, nearC, col), hashCor(r, c, col))) { // 那么把它们连成同一个岛 union(hashCor(nearR, nearC, col), hashCor(r, c, col)); isNum--;// 因为把两块不同的岛连成同一个岛了,所以岛的数目减一 } } } System.out.printf("%d%c", isNum, opNum==0 ? '\n' : ' '); } } } }