【蓝桥杯3538】合并区域（bfs&java&模拟）_蓝桥杯java合并区域

问题描述

输入输出

解题思路一（未通过）

题目的意思是给你两个n*n的矩阵，你需要将其以不同方式进行合并，并最终求得最大区域的面积。

初次尝试时，我想的是不需要实现合并，可以转化为左边最大区域+右边最大区域即为结果（如题目所给例图），当然也有可能是两区域中的某个“内陆”区域最大（如下图所示）

初次代码（未通过）

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
class Pos {
	int x, y;
 
	public Pos(int x, int y) {
		this.x = x;
		this.y = y;
	}
}
 
public class Main {
	// 不临海也有可能是最大值
	static int innerMax = 0;
 
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
 
		int[][] island1 = new int[n + 1][n + 1];
		int[][] island2 = new int[n + 1][n + 1];
 
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				island1[i][j] = scan.nextInt();
			}
		}
 
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				island2[i][j] = scan.nextInt();
			}
		}
		scan.close();
 
		int outerArea1 = bfsOuter(island1, n);
		int outerArea2 = bfsOuter(island2, n);
 
		if (outerArea1 + outerArea2 > innerMax) {
			System.out.println(outerArea1 + outerArea2);
		} else {
			System.out.println(innerMax);
		}
	}
 
	// bfs遍历获取临海区域的最大值
	public static int bfsOuter(int island[][], int n) {
		int outerMax = 0;	//记录最大的临海区域面积
		boolean[][] visited = new boolean[n + 1][n + 1];	//记录是否访问过
		Queue<Pos> queue = new LinkedList<>();				//bfs队列
		int[][] dirs = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };	//上、右、下、左四个方向
 
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (visited[i][j] == false && island[i][j] == 1) {
					queue.offer(new Pos(i, j));
					visited[i][j] = true;
					int count = 1;			//记录当前面积
					boolean outer = false;	// 记录是否临海，不临海无法相连两个区域
 
					while (!queue.isEmpty()) {
						Pos pos = queue.poll();
 
						for (int[] dir : dirs) {
							int x = pos.x + dir[0];
							int y = pos.y + dir[1];
 
							if (x >= 1 && x <= n && y >= 1 && y <= n && island[x][y] == 1 && visited[x][y] == false) {
								visited[x][y] = true;
								queue.offer(new Pos(x, y));
								count++;
								
								// 若临海则更新outer的值
								if (x == 1 || x == n || y == 1 || y == n) {
									outer = true;
								}
							}
						}
					}
 
					if (outer) {	//是否临海
						outerMax = Math.max(outerMax, count);
					} else {
						innerMax = Math.max(innerMax, count);
					}
				}
			}
		}
 
		return outerMax;
	}
}

 只过了百分之十的数据，没有考虑到左边的区域将右边的两个区域连通起来的情况。

果然还是没法取巧，得老老实实合并区域（倒.jpg）

解题思路二

参考思路

将两个n*n大小的矩阵以不同方式合并后再用bfs/dfs求出最大面积即可。

可以通过边进行分类，4条边组合上4条边，总共有4*4=16种。

不过因为连接的边重叠的格子数不同，所以每种又会有2n-1个。

旋转90度的公式可以推导出来，可以看出原矩阵的[i][j]变为旋转90度后的矩阵的[j][n-i-1]。

至于矩阵合并的具体实现，可以用count来记录偏移值，从2n-1到1。

合并后用bfs求最大面积的方式大体同解题思路一，是很常规的解法。

蓝桥杯也有一道很相似的题——【蓝桥杯3513】岛屿个数（BFS&java）

AC代码

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
//存储点的坐标
class Pos {
	int x, y;
 
	public Pos(int x, int y) {
		this.x = x;
		this.y = y;
	}
}
 
public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
 
//		建立并读入两个矩阵
		int[][] island1 = new int[n][n];
		int[][] island2 = new int[n][n];
 
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				island1[i][j] = scan.nextInt();
			}
		}
 
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				island2[i][j] = scan.nextInt();
			}
		}
		scan.close();
 
//		持续旋转90度得到两个矩阵分别旋转90、180、270度的矩阵
		int[][] island1_90 = rotate90(island1);
		int[][] island1_180 = rotate90(island1_90);
		int[][] island1_270 = rotate90(island1_180);
 
		int[][] island2_90 = rotate90(island2);
		int[][] island2_180 = rotate90(island2_90);
		int[][] island2_270 = rotate90(island2_180);
 
//		存入三维数组方便调用
		int[][][] islands1 = { island1, island1_90, island1_180, island1_270 };
		int[][][] islands2 = { island2, island2_90, island2_180, island2_270 };
 
//		count变量记录偏移值
		int count = 2 * n - 1, max = 0;
 
		while (count > 0) {
 
//			根据边分为4*4=16种，每种再根据偏移变量count进行合并
			for (int i = 0; i < 4; i++) {
				for (int j = 0; j < 4; j++) {
//					根据count偏移值合并两个矩阵，并用bfs求得合并后的最大面积，若最大面积大于当前最大面积则更新
					max = Math.max(max, bfsMaxArea(mergeIslands(islands1[i], islands2[j], count), 2 * n));
				}
			}
			count--; // 要在while循环的最后才能减去一，不然会影响运算
		}
 
		System.out.println(max);
 
	}
 
//	顺时针旋转矩阵90度后返回
	public static int[][] rotate90(int[][] map) {
		int n = map.length;
		int[][] map_90 = new int[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				map_90[j][n - i - 1] = map[i][j];
			}
		}
		return map_90;
	}
 
//	合并两个数组并返回
	public static int[][] mergeIslands(int[][] map1, int[][] map2, int count) {
		int n = map1.length;
 
//		合并后的数组横坐标最大值为2n-1（因为至少一行相接），列坐标最大值为2n，但是为了bfs方便都设置为2n
		int[][] map = new int[2 * n][2 * n];
 
//		若count>=n
		if (count >= n) {
			// 将map1放在map的左上角
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					map[i][j] = map1[i][j];
				}
			}
 
			// 再根据map1的位置和偏移量count确定map2的位置
			for (int i = count - n; i < count; i++) {
				for (int j = n; j <= 2 * n - 1; j++) {
					map[i][j] = map2[i - (count - n)][j - n];
				}
			}
		} else {
			// 否则将map1放在左下角
			for (int i = n - 1; i < 2 * n - 1; i++) {
				for (int j = 0; j < n; j++) {
					map[i][j] = map1[i - (n - 1)][j];
				}
			}
 
			// 再根据map1的位置和偏移量count确定map2的位置
			for (int i = count - 1; i < count - 1 + n; i++) {
				for (int j = n; j <= 2 * n - 1; j++) {
					map[i][j] = map2[i - (count - 1)][j - n];
				}
			}
		}
 
//		输出每次合并后的矩阵查验
//		System.out.println();
//		for (int i = 0; i < 2 * n - 1; i++) {
//			for (int j = 0; j <= 2 * n - 1; j++) {
//				System.out.print(map[i][j] + " ");
//			}
//			System.out.println();
//		}
 
		return map;
	}
 
	// bfs遍历获取面积最大值
	public static int bfsMaxArea(int island[][], int n) {
		int areaMax = 0; // 记录最大面积
		boolean[][] visited = new boolean[n][n]; // 记录是否访问过
		Queue<Pos> queue = new LinkedList<>(); // bfs队列
		int[][] dirs = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } }; // 上、右、下、左四个方向
 
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (visited[i][j] == false && island[i][j] == 1) {
					queue.offer(new Pos(i, j));
					visited[i][j] = true;
					int area = 1; // 记录当前面积
 
					while (!queue.isEmpty()) {
						Pos pos = queue.poll();
 
						for (int[] dir : dirs) {
							// 移动后的坐标值
							int x = pos.x + dir[0];
							int y = pos.y + dir[1];
 
							// 未访问过且为陆地且在区域内
							if (x >= 0 && x < n && y >= 0 && y < n && island[x][y] == 1 && visited[x][y] == false) {
								visited[x][y] = true;
								queue.offer(new Pos(x, y));
								area++;
							}
						}
					}
 
//					更新面积最大值
					areaMax = Math.max(areaMax, area);
				}
			}
		}
		return areaMax;
	}
}

评价

这道题的难度其实不算很大，就是合并区域那一块有点麻烦，需要计算很多。思路理顺后很好解决。

（by 归忆）