题目描述
给定一个 m x n 的矩阵，由若干字符 ‘X’ 和 ‘O’构成，’X’表示该处已被占据，’O’表示该处空闲，请找到最大的单入口空闲区域。
解释：
空闲区域是由连通的’O’组成的区域，位于边界的’O’可以构成入口，
单入口空闲区域即有且只有一个位于边界的’O’作为入口的由连通的’O’组成的区域。
如果两个元素在水平或垂直方向相邻，则称它们是“连通”的。
输入描述
第一行输入为两个数字，第一个数字为行数m，第二个数字为列数n，两个数字以空格分隔，1<=m,n<=200。
剩余各行为矩阵各行元素，元素为‘X’或‘O’，各元素间以空格分隔。
输出描述
若有唯一符合要求的最大单入口空闲区域，输出三个数字
- 第一个数字为入口行坐标（0~m-1）
- 第二个数字为入口列坐标（0~n-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)
解题思路
- 问题理解我们需要在给定的矩阵中找出所有由连通的 ‘O’ 组成的区域，其中恰好只有一个边界上的 ‘O’（即入口）。然后在这些区域中，找到最大的一个。如果有多个区域大小相同且并列最大，则只输出该大小；如果只有一个最大，则输出入口坐标和大小；如果没有符合条件的区域，输出 “NULL”。
- 核心步骤
- 遍历矩阵每个格子，遇到未访问的 ‘O’ 时，进行广度优先搜索（BFS）或深度优先搜索（DFS）找出整个连通区域。
- 在遍历过程中，统计该区域中位于边界的格子数量，并记录其中一个边界格子的坐标（如果有）。
- 如果边界格子数量恰好为 1，则该区域为单入口区域，记录其大小和入口坐标。
- 比较所有单入口区域的大小，找出最大值，并记录最大值出现的次数以及第一次出现时的入口坐标（用于唯一情况）。
- 最后根据统计结果输出。
- 注意事项
- 边界条件：行坐标为 0 或 m-1，列坐标为 0 或 n-1。
- 使用 visited 数组避免重复访问。
- 输入格式：第一行 m 和 n，接下来 m 行每行 n 个字符，以空格分隔。
- 输出格式：严格按题目要求，数字间用空格分隔，无多余空格。
JAVA实现
publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);intm=sc.nextInt();intn=sc.nextInt();char[][]grid=newchar[m][n];for(inti=0;i<m;i++){for(intj=0;j<n;j++){grid[i][j]=sc.next().charAt(0);}}sc.close();boolean[][]visited=newboolean[m][n];intmaxSize=0;// 当前找到的最大单入口区域大小intcountMax=0;// 最大区域出现的次数（用于判断是否唯一）intentryR=-1,entryC=-1;// 当最大区域唯一时，记录其入口坐标// 方向数组：上下左右int[][]DIRS={{-1,0},{1,0},{0,-1},{0,1}};for(inti=0;i<m;i++){for(intj=0;j<n;j++){// 遇到未访问的 'O'，开始 BFSif(grid[i][j]=='O'&&!visited[i][j]){// BFS 队列Queue<int[]>queue=newLinkedList<>();queue.offer(newint[]{i,j});visited[i][j]=true;intsize=0;// 当前区域大小intborderCount=0;// 该区域中位于边界的格子数intfirstBorderR=-1,firstBorderC=-1;// 第一个遇到的边界格子坐标while(!queue.isEmpty()){int[]cur=queue.poll();intr=cur[0];intc=cur[1];size++;// 判断是否在边界上if(r==0||r==m-1||c==0||c==n-1){borderCount++;if(borderCount==1){// 记录第一个边界格子作为入口候选firstBorderR=r;firstBorderC=c;}}// 探索四个方向for(int[]d:DIRS){intnr=r+d[0];intnc=c+d[1];if(nr>=0&&nr<m&&nc>=0&&nc<n&&grid[nr][nc]=='O'&&!visited[nr][nc]){visited[nr][nc]=true;queue.offer(newint[]{nr,nc});}}}// 如果该区域恰好只有一个边界格子，则是单入口区域if(borderCount==1){if(size>maxSize){maxSize=size;countMax=1;entryR=firstBorderR;entryC=firstBorderC;}elseif(size==maxSize){countMax++;}}}}}// 输出结果if(maxSize==0){System.out.println("NULL");}elseif(countMax>1){// 多个最大区域且大小相同，只输出大小System.out.println(maxSize);}else{// 唯一最大区域，输出入口坐标和大小System.out.println(entryR+" "+entryC+" "+maxSize);}}
