算法练习（八）区域搜索

一、腐烂的橘子

1、题目描述&＃xff1a; 在给定的 m x n 网格 grid 中&＃xff0c;每个单元格可以有以下三个值之一&＃xff1a;

值 0 代表空单元格&＃xff1b;
值 1 代表新鲜橘子&＃xff1b;
值 2 代表腐烂的橘子。
每分钟&＃xff0c;腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能&＃xff0c;返回 -1

2、示例如下&＃xff1a;

3、代码如下&＃xff1a;

class Solution {public int orangesRotting(int[][] grid) {//边界&＃xff0c;长和宽int M&＃61;grid.length;int N&＃61;grid[0].length;Queue<int[]> queue&＃61;new LinkedList<>();int count&＃61;0; //新鲜橘子的数量for(int i&＃61;0;i<M;i&＃43;&＃43;){for(int j&＃61;0;j<N;j&＃43;&＃43;){if(grid[i][j]&＃61;&＃61;1){ count&＃43;&＃43;; //记录新鲜橘子}else if(grid[i][j]&＃61;&＃61;2){queue.add(new int[]{i,j}); //腐烂的橘子也记录下来}}}int round&＃61;0; //时间、轮次while(count>0&&!queue.isEmpty()){ //当没有新鲜橘子且队列中的腐烂橘子遍历完时退出循环round&＃43;&＃43;;int n&＃61;queue.size(); //记录当前层级的腐烂橘子数量&＃xff0c;因为每层都会更新队列for(int i&＃61;0;i<n;i&＃43;&＃43;){int[] orange&＃61;queue.poll(); //将当前层最先放入的橘子拿出int r&＃61;orange[0];int c&＃61;orange[1];if(r-1>&＃61;0&&grid[r-1][c]&＃61;&＃61;1){ //更新四周橘子的状态grid[r-1][c]&＃61;2;count--;queue.add(new int[]{r-1,c});}if(r&＃43;1<M&&grid[r&＃43;1][c]&＃61;&＃61;1){grid[r&＃43;1][c]&＃61;2;count--;queue.add(new int[]{r&＃43;1,c});}if(c-1>&＃61;0&&grid[r][c-1]&＃61;&＃61;1){grid[r][c-1]&＃61;2;count--;queue.add(new int[]{r,c-1});}if(c&＃43;1<N&&grid[r][c&＃43;1]&＃61;&＃61;1){grid[r][c&＃43;1]&＃61;2;count--;queue.add(new int[]{r,c&＃43;1});}}}if(count>0){ //若依然存在新鲜橘子&＃xff0c;说明腐烂的橘子不可达return -1;}else{ //若不存在则输出轮次return round;}}
}


二、查找单入口空闲区域

1、题目描述&＃xff1a; 给定一个 m x n 的矩阵&＃xff0c;由若干字符 ‘X’ 和 &＃39;O’构成&＃xff0c;&＃39;X’表示该处已被占据&＃xff0c;&＃39;O’表示该处空闲&＃xff0c;请找到最大的单入口空闲区域。

解释&＃xff1a;
空闲区域是由连通的’O’组成的区域&＃xff0c;位于边界的’O’可以构成入口&＃xff0c;单入口空闲区域即有且只有一个位于边界的’O’作为入口的由连通的’O’组成的区域。
如果两个元素在水平或垂直方向相邻&＃xff0c;则称它们是“连通”的。

2、示例如下&＃xff1a;

3、代码如下&＃xff1a;

import java.util.*;public class danRuKou {public static int m;public static int n;public static String[][] strings;public static int[] rukou&＃61;new int[2]; //入口坐标public static int count&＃61;0; //入口个数public static void main(String[] args){Scanner sc&＃61;new Scanner(System.in);m&＃61;sc.nextInt();n&＃61;sc.nextInt();strings&＃61;new String[m][n];for(int i&＃61;0;i<m;i&＃43;&＃43;){for(int j&＃61;0;j<n;j&＃43;&＃43;){strings[i][j]&＃61;sc.next();//System.out.println(strings[i][j]);}}int max&＃61;0;List<int[]> quyu&＃61;new ArrayList<>();for(int i&＃61;0;i<m;i&＃43;&＃43;){for(int j&＃61;0;j<n;j&＃43;&＃43;){if(strings[i][j].equals("O")){ //从左上开始遍历寻找第一个为O的坐标strings[i][j]&＃61;"X";List<int[]> zuobiao&＃61;new ArrayList<>(); //保存当前空闲区域的所有坐标zuobiao.add(new int[]{i,j});qiuquyu(i,j,zuobiao); //求当前空闲区域的所有坐标if(count&＃61;&＃61;1){ //如果入口只有一个则进行比较if(max&＃61;&＃61;zuobiao.size()){ //有大小相同的单入口空闲区域&＃xff0c;则只需要大小&＃xff0c;无需坐标quyu.clear();}else if(max<zuobiao.size()){ //若有更大的单入口空闲区域&＃xff0c;则清除前面的那个&＃xff0c;将当前的单入口空闲区域坐标放进去quyu.clear();quyu.add(new int[]{rukou[0],rukou[1],zuobiao.size()});max&＃61;zuobiao.size();}}count&＃61;0;rukou&＃61;new int[2];}}}if(quyu.size()&＃61;&＃61;1){ //如果单入口空闲区域只有1个&＃xff0c;则直接输出int[] res&＃61;quyu.get(0);System.out.println(res[0]&＃43;" "&＃43;res[1]&＃43;" "&＃43;res[2]);}else if(max!&＃61;0){ //如果最大区域的面积不止为0&＃xff0c;则输出最大区域System.out.println(max);}else { //如果没找到&＃xff0c;则输出NULLSystem.out.println("NULL");}}//得到单入口区域public static void qiuquyu(int x,int y,List<int[]> list){if(x&＃61;&＃61;0||x&＃61;&＃61;m-1||y&＃61;&＃61;0||y&＃61;&＃61;n-1){count&＃43;&＃43;;rukou[0]&＃61;x;rukou[1]&＃61;y;}if (x<m-1){if(strings[x&＃43;1][y].equals("O")){ //因为是按顺序来&＃xff0c;所以只需要向右或者向下遍历即可strings[x&＃43;1][y]&＃61;"X";list.add(new int[]{x&＃43;1,y});qiuquyu(x&＃43;1,y,list);}}if (y<n-1){if(strings[x][y&＃43;1].equals("O")){strings[x][y&＃43;1]&＃61;"X";list.add(new int[]{x,y&＃43;1});qiuquyu(x,y&＃43;1,list);}}}
}

三、开心消消乐

1、题目描述&＃xff1a; 给定一个N行M列的二维矩阵&＃xff0c;矩阵中每个位置的数字取值为0或1。矩阵示例如&＃xff1a;
1 1 0 0
0 0 0 1
0 0 1 1
1 1 1 1
现需要将矩阵中所有的1进行反转为0&＃xff0c;规则如下&＃xff1a;
1&＃xff09;当点击一个1时&＃xff0c;该1变被反转为0&＃xff0c;同时相邻的上、下、左、右&＃xff0c;以及左上、左下、右上、右下8个方向的1&＃xff08;如果存在1&＃xff09;均会自动反转为0&＃xff1b;
2&＃xff09;进一步地&＃xff0c;一个位置上的1被反转为0时&＃xff0c;与其相邻的8个方向的1&＃xff08;如果存在1&＃xff09;均会自动反转为0&＃xff1b;
按照上述规则示例中的矩阵只最少需要点击2次后&＃xff0c;所有值均为0。请问&＃xff0c;给定一个矩阵&＃xff0c;最少需要点击几次后&＃xff0c;所有数字均为0&＃xff1f;

2、示例如下&＃xff1a;

3、代码如下&＃xff1a;

import java.util.*;public class kaiXingXiaoXiaoLe {public static int[][] juzhen;public static int N;public static int M;public static void main(String[] args) {Scanner sc&＃61;new Scanner(System.in);N&＃61;sc.nextInt();M&＃61;sc.nextInt();juzhen&＃61;new int[N][M];for (int i&＃61;0;i<N;i&＃43;&＃43;){ //保存二维数组for (int j&＃61;0;j<M;j&＃43;&＃43;){juzhen[i][j]&＃61;sc.nextInt();}}int res&＃61;0;for (int i&＃61;0;i<N;i&＃43;&＃43;){ //开始清除for (int j&＃61;0;j<M;j&＃43;&＃43;){if (juzhen[i][j]&＃61;&＃61;1){clearHappy(i,j);res&＃43;&＃43;;}}}System.out.println(res);}//8个方向都清一遍public static void clearHappy(int x,int y){if (x>0){if(juzhen[x-1][y]&＃61;&＃61;1){ //正上juzhen[x-1][y]&＃61;0;clearHappy(x-1,y);}if(y>0){if(juzhen[x-1][y-1]&＃61;&＃61;1){ //左上juzhen[x-1][y-1]&＃61;0;clearHappy(x-1,y-1);}}if(y<M-1){if(juzhen[x-1][y&＃43;1]&＃61;&＃61;1){ //右上juzhen[x-1][y&＃43;1]&＃61;0;clearHappy(x-1,y&＃43;1);}}}if(x<N-1){if(juzhen[x&＃43;1][y]&＃61;&＃61;1){ //正下juzhen[x&＃43;1][y]&＃61;0;clearHappy(x&＃43;1,y);}if(y>0){if(juzhen[x&＃43;1][y-1]&＃61;&＃61;1){ //左下juzhen[x&＃43;1][y-1]&＃61;0;clearHappy(x&＃43;1,y-1);}}if(y<M-1){if(juzhen[x&＃43;1][y&＃43;1]&＃61;&＃61;1){ //右下juzhen[x&＃43;1][y&＃43;1]&＃61;0;clearHappy(x&＃43;1,y&＃43;1);}}}if(y>0){if(juzhen[x][y-1]&＃61;&＃61;1){ //正左juzhen[x][y-1]&＃61;0;clearHappy(x,y-1);}}if(y<M-1){if(juzhen[x][y&＃43;1]&＃61;&＃61;1){ //正右juzhen[x][y&＃43;1]&＃61;0;clearHappy(x,y&＃43;1);}}}
}