求二维数组蓄水数

逃离我推掉我的手 2022-01-09 23:07 253阅读 0赞

# 1、需求 #

接上一个需求：[求一维数组蓄水数][Link 1]，如果数组是二维数组呢？

如果求得蓄水数呢？

比如这种情况：红色的格子是能蓄水的格子，蓝色的各自是墙， 也就是不能蓄水的格子

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pob25ncWkyNTEz_size_16_color_FFFFFF_t_70][]

# 2、解题思路 #

其实对于这种题目，会很很多的难点，比如：

![20190620191642363.png][]

简单低洼地带，直接求蓄水数，上下左右 5 5 5 5， 那中间的3 是能蓄水的

比如：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pob25ncWkyNTEz_size_16_color_FFFFFF_t_70 1][]

比如这种：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pob25ncWkyNTEz_size_16_color_FFFFFF_t_70 2][] ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pob25ncWkyNTEz_size_16_color_FFFFFF_t_70 3][]

以上这些图形出现的时候，其实求解还是比较复杂的。

我提供的思路呢是：

如果这个二维数组，就是一个0-1矩阵的话，那么求出蓄水数，还是挺容易的。比如：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pob25ncWkyNTEz_size_16_color_FFFFFF_t_70 4][]

**整体思路：把0-1二维数组映射成为一个最终的true-false数组。true的位置表示能蓄水。false的位置，表示不能蓄水。**

**显然：最外层无论如何，都不能蓄水。**

**1、先把0-1二维数组映射成为一个true-false数组：0的位置为true, 1的位置为false（这里面的true中，还有部分是不可蓄水的，排除掉所有的不可蓄水的true，然后count一下所有的剩下的true就是这个0-1矩阵的蓄水数）**

**2、从外层往里层遍历，遍历一次，就把最外层的所有的0都置位false**

**3、不停的重复“2”步骤，直到，再也不需要把任何的0置位false为止**

**4、count一下还剩下的true有多少个，就是能蓄水的位置和数量**

**既然每个0-1数组的蓄水数都能求出来了，那么把一个正常数组切分成一个多个0-1数组，是很简单的事了，如果有对此不懂的同学，请去研究代码的实现。**

**那整体思路：**

**1、先把一个正常的二维矩阵变成多个0-1二维矩阵**

**2、求出每个二维矩阵的蓄水数**

**3、把切分出来的所有二维矩阵的蓄水数相加就能求出总蓄水数。**

# 3、具体代码实现 #

package com.aura.funny.water;
    
    import java.util.ArrayList;
    import java.util.List;
    
    /**
     * @author 马中华 https://blog.csdn.net/zhongqi2513
     * @Title: WaterMatrix02.java
     * @Package com.aura.funny.water
     * @ClassName: WaterMatrix02
     * @Description: 用来计算二维矩阵的蓄水量
     * @date 2016年1月27日 下午1:39:30
     */
    public class WaterMatrix02 {
    
      // 矩阵行数
      public static final int MATRIX_ROW = 8;
      // 矩阵列宽
      public static final int MATRIX_COLUMN = 8;
      // 矩阵最大高度
      public static final int MATRIX_MAX_HEIGHT = 30;
      // 矩阵最小高度
      public static final int MATRIX_MIN_HEIGHT = 10;
    
      /**
       * @param args
       * @Title: main
       * @Description: 测试入口
       * @author 马中华 https://blog.csdn.net/zhongqi2513
       * @date 2016年1月27日 下午4:35:22
       */
      public static void main(String[] args) {
    
        // 第一步：产生一个随机矩阵
        int[][] matrix = provideMatrix();
    
    	/*int[][] matrix = new int[][]{
       {9,9,9,9,9,9,9,9,9},
    					{9,9,9,9,9,9,9,9,9},
    					{9,9,2,2,2,2,2,9,9},
    					{9,9,2,9,9,9,2,9,9},
    					{9,9,2,9,2,9,2,9,9},
    					{9,9,2,9,9,9,2,9,9},
    					{9,9,2,2,2,2,2,9,9},
    					{9,9,9,9,9,9,9,9,9},
    					{9,9,9,9,9,9,9,9,9}
    	};*/
    
        printMatrix(matrix);
        System.out.println("----------------------华丽丽分割线-----------------------------");
    
        // 总蓄水量
        int sumWater = 0;
    
        // 第二步：获取该矩阵的所有0-1矩阵， 并打印显示
        List<int[][]> oneZeroMatrixList = getOneZeroMatrixList(matrix);
    
        // 用来表示，是否已经开始产生蓄水
        boolean flag = false;
        for (int i = MATRIX_MIN_HEIGHT, size = oneZeroMatrixList.size(); i < size; i++) {
          int[][] oneZeroMatrix = oneZeroMatrixList.get(i);
          // 打印0-1矩阵
          printMatrix(oneZeroMatrix);
          // 求0-1矩阵的蓄水数
          int water = getWaterFromOneZeroMatrix(oneZeroMatrix);
          if(water != 0){
            flag = true;
          }
    
          System.out.println("第  " + (i + 1) + " 层的蓄水为：" + water);
          System.out.println("-----------------------------------------------------------");
    
          // 如果当前这一层都不能蓄水，那么上一层也一定不能蓄水
          if(flag && water == 0){
            System.out.println("再往上的每一层("+(i + 2) +" - "+ MATRIX_MAX_HEIGHT+")，都是蓄水数为0，不必再计算");
            break;
          }
          sumWater += water;
        }
    
        // 第五步： 输出结果
        System.out.println("\n" + "该二维矩阵蓄水量：" + sumWater);
      }
    
      /**
       * @return
       * @Title: provideMatrix
       * @Description: 这个方法用来产生一个随机矩阵, 长宽高由以上四个属性决定, 会等于边界值
       * @author 马中华 https://blog.csdn.net/zhongqi2513
       * @date 2016年1月27日 下午1:43:18
       */
      public static int[][] provideMatrix() {
        return provideMatrix(MATRIX_ROW, MATRIX_COLUMN, MATRIX_MIN_HEIGHT, MATRIX_MAX_HEIGHT);
      }
    
      public static int[][] provideMatrix(int row, int column, int min, int max) {
        int[][] sourceMatrix = new int[row][column];
        for (int i = 0; i < row; i++) {
          for (int j = 0; j < column; j++) {
            sourceMatrix[i][j] = randomNumber(min, max);
          }
        }
        return sourceMatrix;
      }
    
      /**
       * @param min
       * @param max
       * @return
       * @Title: randomNumber
       * @Description: 用来产生一个区间内的随机整数
       * @author 马中华 https://blog.csdn.net/zhongqi2513
       * @date 2016年1月27日 下午1:45:36
       */
      public static int randomNumber(int min, int max) {
        if (min < max) {
          return (int) (Math.random() * (max - min + 1) + min);
        } else if (min == max) {
          return min;
        } else {
          return randomNumber(max, min);
        }
      }
    
      /**
       * @Title: printMatrix
       * @Description: 打印二维矩阵
       * @author 马中华 https://blog.csdn.net/zhongqi2513
       * @date 2016年1月27日 下午4:19:15
       */
      public static void printMatrix(int[][] matrix) {
        for (int i = 0, size = matrix.length; i < size; i++) {
          for (int j = 0, length = matrix[0].length; j < length; j++) {
            System.out.print(matrix[i][j] + "\t");
          }
          System.out.println();
        }
      }
    
      public static void printBooleanMatrix(boolean[][] matrix) {
        for (int i = 0, size = matrix.length; i < size; i++) {
          for (int j = 0, length = matrix[0].length; j < length; j++) {
            System.out.print(matrix[i][j] + "\t");
          }
          System.out.println();
        }
      }
    
      /**
       * @param oneZeroMatrix
       * @return
       * @Title: copyOneZeroMatrixToBoolean
       * @Description: 矩阵转化：把0-1矩阵转换成true-false矩阵（0-true, 1-false）
       * @author 马中华 https://blog.csdn.net/zhongqi2513
       * @date 2016年1月27日 下午6:00:09
       */
      public static boolean[][] copyOneZeroMatrixToBoolean(int[][] oneZeroMatrix) {
        boolean[][] booleanMatrix = new boolean[oneZeroMatrix.length][oneZeroMatrix[0].length];
        for (int i = 0, size = oneZeroMatrix.length; i < size; i++) {
          for (int j = 0, length = oneZeroMatrix[0].length; j < length; j++) {
            if (oneZeroMatrix[i][j] == 0) {
              booleanMatrix[i][j] = true;
            } else {
              booleanMatrix[i][j] = false;
            }
          }
        }
        return booleanMatrix;
      }
    
      /**
       * @return
       * @Title: getOneZeroMatrixList
       * @Description: 把一个随机矩阵切分成最大高度个数的0-1矩阵
       * @author 马中华 https://blog.csdn.net/zhongqi2513
       * @date 2016年1月27日 下午4:24:17
       */
      public static List<int[][]> getOneZeroMatrixList(int[][] matrix) {
        int max = getMaxFromMatrix(matrix);
        List<int[][]> oneZeroMatrixList = new ArrayList<int[][]>();
        for (int k = 0; k < max; k++) {
          int[][] oneZeroMatrix = new int[matrix.length][matrix[0].length];
          // 此处开始循环按层切割矩阵
          for (int i = 0, size = matrix.length; i < size; i++) {
            for (int j = 0, length = matrix[0].length; j < length; j++) {
              if (matrix[i][j] > 0) {
                oneZeroMatrix[i][j] = 1;
                matrix[i][j] -= 1;
              } else {
                oneZeroMatrix[i][j] = 0;
              }
            }
          }
          oneZeroMatrixList.add(oneZeroMatrix);
        }
        return oneZeroMatrixList;
      }
    
      /**
       * @return
       * @Title: getMaxFromMatrix
       * @Description: 获取矩阵最大值
       * @author 马中华 https://blog.csdn.net/zhongqi2513
       * @date 2016年1月27日 下午4:25:43
       */
      public static int getMaxFromMatrix(int[][] matrix) {
        int max = 0;
        for (int i = 0, size = matrix.length; i < size; i++) {
          for (int j = 0, length = matrix[0].length; j < length; j++) {
            if (matrix[i][j] >= max) {
              max = matrix[i][j];
            }
          }
        }
        return max;
      }
    
      public static int getMinFromMatrix(int[][] matrix) {
        int max = matrix[0][0];
        for (int i = 0, size = matrix.length; i < size; i++) {
          for (int j = 0, length = matrix[0].length; j < length; j++) {
            if (matrix[i][j] <= max) {
              max = matrix[i][j];
            }
          }
        }
        return max;
      }
    
      /**
       * @Title: getWaterFromOneZeroMatrix
       * @Description: 从一个0-1矩阵中获取所有被1包围的0的个数，即是求取该0-1矩阵的蓄水量
       * @author 马中华 https://blog.csdn.net/zhongqi2513
       * @date 2016年1月27日 下午4:38:36
       */
      public static int getWaterFromOneZeroMatrix(int[][] oneZeroMatrix) {
        // 从 oneZeroMatrix 赋值一个 booleanMatrix
        boolean[][] booleanMatrix = copyOneZeroMatrixToBoolean(oneZeroMatrix);
    
        int maxX = oneZeroMatrix[0].length;
        int maxY = oneZeroMatrix.length;
    
        // 给左右边界0值置 false
        for (int i = 0; i < maxX; i++) {
          booleanMatrix[0][i] = false;
          booleanMatrix[maxY - 1][i] = false;
        }
        // 给上下边界0值置 false
        for (int j = 0; j < maxY; j++) {
          booleanMatrix[j][0] = false;
          booleanMatrix[j][maxX - 1] = false;
        }
    
        int changeNumber = 1;
    
        while (changeNumber != 0) {
          System.out.println("执行改值次数： " + changeNumber);
          changeNumber = setFalseArea(oneZeroMatrix, booleanMatrix, maxX, maxY);
        }
    
        return countTrueFromMatrix(booleanMatrix);
      }
    
      /**
       * 描述: 每次循环设置false值， 只要有值还可以设置成false,那么就要执行下去，如果返回值 changeNumber == 0 ， 那么表示已经执行完毕
       * 作者: 马中华 https://blog.csdn.net/zhongqi2513
       * 日期 : 2016年1月27日 下午11:21:28
       *
       * @param oneZeroMatrix
       * @param booleanMatrix
       * @param maxX
       * @param maxY
       * @return
       */
      public static int setFalseArea(int[][] oneZeroMatrix, boolean[][] booleanMatrix, int maxX, int maxY) {
        int changeNumber = 0;
        for (int i = 1; i < maxY - 1; i++) {
          for (int j = 1; j < maxX - 1; j++) {
            if (booleanMatrix[i][j] && isZeroAndFalse(oneZeroMatrix, booleanMatrix, i, j)) {
              changeNumber++;
              booleanMatrix[i][j] = false;
            }
          }
        }
        return changeNumber;
      }
    
      /**
       * 描述: 用来判断该点是否与
       * 作者: 马中华 https://blog.csdn.net/zhongqi2513
       * 日期 : 2016年1月27日 下午10:50:24
       *
       * @return
       */
      public static boolean isZeroAndFalse(int[][] oneZeroMatrix, boolean[][] booleanMatrix, int x, int y) {
        if (oneZeroMatrix[x - 1][y] == 0 && !booleanMatrix[x - 1][y]) { // 左
          return true;
        }
        if (oneZeroMatrix[x + 1][y] == 0 && !booleanMatrix[x + 1][y]) { // 右
          return true;
        }
        if (oneZeroMatrix[x][y - 1] == 0 && !booleanMatrix[x][y - 1]) { // 上
          return true;
        }
        if (oneZeroMatrix[x][y + 1] == 0 && !booleanMatrix[x][y + 1]) { // 下
          return true;
        }
        return false;
      }
    
      /**
       * 描述: count matrix 中 true 的个数，
       * 作者: 马中华 https://blog.csdn.net/zhongqi2513
       * 日期 : 2016年1月27日 下午9:47:09
       *
       * @param booleanMatrix
       * @return
       */
      public static int countTrueFromMatrix(boolean[][] booleanMatrix) {
        int falseCounts = 0;
        for (int i = 0, size = booleanMatrix.length; i < size; i++) {
          for (int j = 0, length = booleanMatrix[0].length; j < length; j++) {
            if (booleanMatrix[i][j]) {
              falseCounts++;
            }
          }
        }
        return falseCounts;
      }
    
    }

# 4、执行结果 #

21	18	15	26	17	11	27	29	
    18	21	16	11	26	23	29	20	
    13	28	14	26	13	22	27	23	
    16	13	27	23	18	22	15	21	
    16	18	28	14	10	30	17	26	
    17	12	16	10	11	14	19	15	
    16	24	25	21	14	18	14	18	
    28	16	22	15	26	21	12	22	
    ----------------------华丽丽分割线-----------------------------
    1	1	1	1	1	1	1	1	
    1	1	1	1	1	1	1	1	
    1	1	1	1	1	1	1	1	
    1	1	1	1	1	1	1	1	
    1	1	1	1	0	1	1	1	
    1	1	1	0	1	1	1	1	
    1	1	1	1	1	1	1	1	
    1	1	1	1	1	1	1	1	
    执行改值次数： 1
    第  11 层的蓄水为：2
    -----------------------------------------------------------
    1	1	1	1	1	0	1	1	
    1	1	1	0	1	1	1	1	
    1	1	1	1	1	1	1	1	
    1	1	1	1	1	1	1	1	
    1	1	1	1	0	1	1	1	
    1	1	1	0	0	1	1	1	
    1	1	1	1	1	1	1	1	
    1	1	1	1	1	1	1	1	
    执行改值次数： 1
    第  12 层的蓄水为：4
    -----------------------------------------------------------
    1	1	1	1	1	0	1	1	
    1	1	1	0	1	1	1	1	
    1	1	1	1	1	1	1	1	
    1	1	1	1	1	1	1	1	
    1	1	1	1	0	1	1	1	
    1	0	1	0	0	1	1	1	
    1	1	1	1	1	1	1	1	
    1	1	1	1	1	1	0	1	
    执行改值次数： 1
    第  13 层的蓄水为：5
    -----------------------------------------------------------
    1	1	1	1	1	0	1	1	
    1	1	1	0	1	1	1	1	
    0	1	1	1	0	1	1	1	
    1	0	1	1	1	1	1	1	
    1	1	1	1	0	1	1	1	
    1	0	1	0	0	1	1	1	
    1	1	1	1	1	1	1	1	
    1	1	1	1	1	1	0	1	
    执行改值次数： 1
    第  14 层的蓄水为：7
    -----------------------------------------------------------
    1	1	1	1	1	0	1	1	
    1	1	1	0	1	1	1	1	
    0	1	0	1	0	1	1	1	
    1	0	1	1	1	1	1	1	
    1	1	1	0	0	1	1	1	
    1	0	1	0	0	0	1	1	
    1	1	1	1	0	1	0	1	
    1	1	1	1	1	1	0	1	
    执行改值次数： 1
    执行改值次数： 1
    第  15 层的蓄水为：11
    -----------------------------------------------------------
    1	1	0	1	1	0	1	1	
    1	1	1	0	1	1	1	1	
    0	1	0	1	0	1	1	1	
    1	0	1	1	1	1	0	1	
    1	1	1	0	0	1	1	1	
    1	0	1	0	0	0	1	0	
    1	1	1	1	0	1	0	1	
    1	1	1	0	1	1	0	1	
    执行改值次数： 1
    执行改值次数： 1
    第  16 层的蓄水为：12
    -----------------------------------------------------------
    1	1	0	1	1	0	1	1	
    1	1	0	0	1	1	1	1	
    0	1	0	1	0	1	1	1	
    0	0	1	1	1	1	0	1	
    0	1	1	0	0	1	1	1	
    1	0	0	0	0	0	1	0	
    0	1	1	1	0	1	0	1	
    1	0	1	0	1	1	0	1	
    执行改值次数： 1
    执行改值次数： 5
    第  17 层的蓄水为：10
    -----------------------------------------------------------
    1	1	0	1	0	0	1	1	
    1	1	0	0	1	1	1	1	
    0	1	0	1	0	1	1	1	
    0	0	1	1	1	1	0	1	
    0	1	1	0	0	1	0	1	
    0	0	0	0	0	0	1	0	
    0	1	1	1	0	1	0	1	
    1	0	1	0	1	1	0	1	
    执行改值次数： 1
    执行改值次数： 11
    执行改值次数： 2
    第  18 层的蓄水为：3
    -----------------------------------------------------------
    1	0	0	1	0	0	1	1	
    0	1	0	0	1	1	1	1	
    0	1	0	1	0	1	1	1	
    0	0	1	1	0	1	0	1	
    0	0	1	0	0	1	0	1	
    0	0	0	0	0	0	1	0	
    0	1	1	1	0	0	0	0	
    1	0	1	0	1	1	0	1	
    执行改值次数： 1
    执行改值次数： 13
    执行改值次数： 2
    执行改值次数： 1
    执行改值次数： 1
    第  19 层的蓄水为：2
    -----------------------------------------------------------
    1	0	0	1	0	0	1	1	
    0	1	0	0	1	1	1	1	
    0	1	0	1	0	1	1	1	
    0	0	1	1	0	1	0	1	
    0	0	1	0	0	1	0	1	
    0	0	0	0	0	0	0	0	
    0	1	1	1	0	0	0	0	
    1	0	1	0	1	1	0	1	
    执行改值次数： 1
    执行改值次数： 14
    执行改值次数： 3
    执行改值次数： 2
    执行改值次数： 1
    第  20 层的蓄水为：0
    -----------------------------------------------------------
    再往上的每一层(21 - 30)，都是蓄水数为0，不必再计算
    
    该二维矩阵蓄水量：56
    
    Process finished with exit code 0

[Link 1]: https://blog.csdn.net/zhongqi2513/article/details/93093920
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pob25ncWkyNTEz_size_16_color_FFFFFF_t_70]: /images/20220109/a01c1fb2a37944c5b8ff9d99f53b5da0.png
[20190620191642363.png]: /images/20220109/430d7343561d479ea9c21b51d315d587.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pob25ncWkyNTEz_size_16_color_FFFFFF_t_70 1]: /images/20220109/e275f5b728bd42ba84448ded7eaad2cd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pob25ncWkyNTEz_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20190620192200636.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pob25ncWkyNTEz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pob25ncWkyNTEz_size_16_color_FFFFFF_t_70 3]: /images/20220109/1170d35d37ab4a3a9441551fef819dc3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pob25ncWkyNTEz_size_16_color_FFFFFF_t_70 4]: /images/20220109/c22e850efd5e4a15bcd6de9df9caceee.png