题目
题目描述
给定一个mxn的矩阵，由若干字符 'X' 和 'O' 构成，'X' 表示该处已被占据，'O' 表示该处空闲，请找到最大的单入口空闲区域。
解释:
空闲区域是由连通的 'O' 组成的区域，位于边界的 'O' 可以构成入口。单入口空闲区域即有且只有一个位于边界的 'O' 作为入口的由连通的 'O' 组成的区域。如果两个元素在水平或垂直方向相邻，则称它们是“连通”的。
输入描述
第一行输入为两个数字，第一个数字为行数m，第二个数字为列数n，两个数字以空格分隔，1<=m,n<=200. 剩余各行为矩阵各行元素，元素为 'X' 或 'O'，各元素间以空格分隔
输出描述
若有唯一符合要求的最大单入口空闲区域，输出三个数字，第一个数字为入口行坐标（范围为 0 ~ 行数 - 1），第二个数字为入口列坐标（范围为 0 ~ 列数 - 1），第三个数字为区域大小，三个数字以空格分隔，若有多个符合要求的最大单入口空闲区域，输出一个数字，代表区域的大小，若没有，输出NULL。
示例1
输入：
4 4
X X X X
X O O X
X O O X
X O X X
输出：
3 1 5
说明：
存在最大单入口区域，入口坐标(3, 1)，区域大小 5
示例2
输入：
4 5
X X X X X
O O O O X
X O O O X
X O X X O
输出：
3 4 1
说明：
存在最大单入口区域，入口坐标(3, 4)，区域大小 1
示例3
输入：
5 4
X X X X
X O O O
X O O O
X O O X
X X X X
输出：
NULL
说明：
不存在最大单入口区域
示例4
输入：
5 4
X X X X
X O O O
X X X X
X O O O
X X X X
输出：
3
说明：
存在两个大小为 3 的最大单入口区域，两个入口坐标分别为（1, 3）、（3, 3）
解题思路
首先要找到边界上的入口，将入口保存，后面依次对每个入口进行 BFS 扩散。
要计算每个入口进来后的区域面积，就要对每个入口分别进行BFS。因此入口应该另外保存在List中，而不是直接放进 Queue，每个入口单独一个 Queue。计算面积的方式是在每次扩散时，节点弹出队列时面积增加 1。
因题目要求多个入口进入到一个区域内，不是单入口区域，不计入。因此要对入口和区域进行映射，要用一个 List<Integer, List<int[]>> entranceMap 来映射区域号 -> 入口坐标列表。
既然对区域要区分，那每个入口扩散时就要标记区域号。若入口本身已经被标记了区域号，说明该入口属于该区域的第二个入口，假如entranceMap的入口坐标列表中。
排除了多入口还没完，如果有多个单入口区域，那么要计算最大的按个区域面积，并给出入口坐标。如果最大的区域面积存在多个，那么只需要给出面积。因此需要用一个 List<Integer, Integer> areaMap 来映射区域号->面积大小。根据区域号可以找到入口列表。
这道题属于二维矩阵 / 网格问题。在此基础上增加区域区分的复杂条件，其核心就是网格问题，多方向扩散计算面积。
代码
public class SingleEntryFreeZones {
public void solution(char[][] matrix) {
// 初始化，找到所有边界的O，多个源头
int m = matrix.length, n = matrix[0].length;
List<int[]> boundaries = new ArrayList<>();
for (int i = 0; i < m; i++) {
if (matrix[i][0] == 'O') boundaries.add(new int[] {i, 0});
if (matrix[i][n - 1] == 'O') boundaries.add(new int[] {i, n - 1});
}
for (int j = 1; j < n - 1; j++) {
if (matrix[0][j] == 'O') boundaries.add(new int[] {0, j});
if (matrix[m - 1][j] == 'O') boundaries.add(new int[] {m - 1, j});
}
// 标记区域，区域对应的面积
int[][] regionMatrix = new int[m][n];
int regionId = 1;
Map<Integer, Integer> areaMap = new HashMap<>();
Map<Integer, List<int[]>> entranceMap = new HashMap<>();
// 定义BFS方向矩阵
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
// BFS
for (int[] entrance : boundaries) {
// 入口节点
int x = entrance[0], y = entrance[1];
int entranceRegion = regionMatrix[x][y];
// 区域号 -> 入口列表映射
if (entranceRegion != 0) {
List<int[]> entrances = entranceMap.get(entranceRegion);
entrances.add(entrance);
continue;
} else {
List<int[]> entrances = new ArrayList<>();
entrances.add(entrance);
entranceMap.put(regionId, entrances);
}
// 为入口标记区域号
regionMatrix[x][y] = regionId;
// 头结点入列
Queue<int[]> q = new LinkedList<>();
q.offer(entrance);
// 区域面积
int area = 0;
while (!q.isEmpty()) {
int[] cur = q.poll();
area++;
// 开始扩散
for (int[] dir : dirs) {
int nx = cur[0] + dir[0], ny = cur[1] + dir[1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && matrix[nx][ny] == 'O' && regionMatrix[nx][ny] == 0) {
regionMatrix[nx][ny] = regionId;
q.offer(new int[]{nx, ny});
}
}
}
areaMap.put(regionId, area);
regionId++;
}
// 排除掉多个入口，并找到的最大面积
int maxArea = 0;
for (Map.Entry<Integer, Integer> areaEntry : areaMap.entrySet()) {
int curRegionId = areaEntry.getKey();
if (entranceMap.get(curRegionId).size() == 1) {
maxArea = Math.max(maxArea, areaEntry.getValue());
}
}
// 找出最大面积对应的区域号列表
List<Integer> maxRegions = new ArrayList<>();
for (Map.Entry<Integer, Integer> areaEntry : areaMap.entrySet()) {
if (maxArea == areaEntry.getValue() && !maxRegions.contains(areaEntry.getKey())) {
maxRegions.add(areaEntry.getKey());
}
}
// 结果
if (maxRegions.isEmpty()) {
System.out.println("NULL");
} else if (maxRegions.size() == 1) {
int[] entrance = entranceMap.get(maxRegions.get(0)).get(0);
System.out.println(entrance[0] + " " + entrance[1] + " " + maxArea);
} else {
System.out.println(maxArea);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
int n = sc.nextInt();
sc.nextLine();
char[][] matrix = new char[m][n];
for (int i = 0; i < m; i++) {
String line = sc.nextLine();
String[] elements = line.split(" ");
for (int j = 0; j < n; j++) {
matrix[i][j] = elements[j].charAt(0);
}
}
// 算法
SingleEntryFreeZones s = new SingleEntryFreeZones();
s.solution(matrix);
}
}
评论