目描述

给一个 m x n 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。
Example 1：
image.png
输入: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
输出: 4
解释: 下雨后，雨水将会被上图蓝色的方块中。总的接雨水量为1+2+1=4

Example 2：
image.png
输入: heightMap = [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]]
输出: 10。

Input & Output

  1. 6
  2. 3 6
  3. 1 4 3 1 3 2
  4. 3 2 1 3 2 4
  5. 2 3 3 2 3 1
  7. 5 5
  8. 3 3 3 3 3
  9. 3 2 2 2 3
  10. 3 2 1 2 3
  11. 3 2 2 2 3
  12. 3 3 3 3 3
  14. 5 5
  15. 3 3 3 3 3
  16. 3 2 2 2 2
  17. 3 2 1 2 3
  18. 3 2 2 2 3
  19. 3 3 3 3 3
  21. 5 5
  22. 3 3 3 3 3
  23. 3 2 2 2 3
  24. 3 2 1 1 1
  25. 3 2 2 2 3
  26. 3 3 3 3 3
  28. 5 5
  29. 3 3 3 3 3
  30. 3 2 2 2 3
  31. 3 2 3 2 3
  32. 3 2 2 2 3
  33. 3 3 3 3 3
  35. 5 5
  36. 3 3 3 3 3
  37. 3 2 2 2 3
  38. 3 2 4 2 3
  39. 3 2 2 2 3
  40. 3 3 3 3 3
  1. 4
  2. 10
  3. 1
  4. 0
  5. 8
  6. 8

Solution

Solution_1（BFS）（Wrong）

遍历每个未被访问的点，数值小于等于该点的所有点接雨水后可以形成高度相同的水面，同一个水面的高度都是其四周方块最小的值，可以计算出每个水平面需要填补的雨水数量。
该方法会导致一个问题：当两个高度不同的水面相邻，本质上它们可以归为同一个水平面，但如果原本高度低的水平面先被遍历了，那么接到雨水的数量会变少。
特殊样例：

  1. 1
  2. 5 5
  3. 3 3 3 3 3
  4. 3 1 2 2 3
  5. 3 2 2 2 3
  6. 3 2 2 2 3
  7. 3 3 3 3 3
  1. 10

用次方法实现，输出错误结果9

  1. import java.util.Scanner;
  3. public class rain 
  4. {
  5.     static int T;
  6.     static int Row, Col;
  7.     static int[][] map;
  8.     static boolean[][] vis;
  10.     static int[][] dir = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
  12.     static int ans;
  14.     public static void main(String[] args) 
  15.     {
  16.         Scanner sc = new Scanner(System.in);
  17.         T = sc.nextInt();
  19.         for(int t=0; t<T; t++)
  20.         {
  21.             Row = sc.nextInt();
  22.             Col = sc.nextInt();
  23.             map = new int[Row][Col];
  24.             vis = new boolean[Row][Col];
  26.             ans = 0;
  28.             for(int i=0; i<Row; i++)
  29.                 for(int j=0; j<Col; j++)
  30.                     map[i][j] = sc.nextInt();
  32.             for(int i=1; i<Row-1; i++)
  33.             {    
  34.                 for(int j=1; j<Col-1; j++)
  35.                 {
  36.                     if(!vis[i][j])
  37.                     {
  38.                         ans += bfs(i, j);
  39.                     }
  40.                 }
  41.             }
  42.             System.out.println(ans);
  43.         }
  44.         sc.close();
  45.     }
  47.     private static int bfs(int row, int col) 
  48.     {
  49.         boolean flag = false;
  50.         int min = Integer.MAX_VALUE;
  51.         int count = 0, sum = 0;
  52.         boolean[][] vis_1 = new boolean[Row][Col];
  54.         for(int i=1; i<Row-1; i++)
  55.             for(int j=1; j<Col-1; j++)
  56.                 vis_1[i][j] = vis[i][j];
  58.         int[][] queue = new int [Row*Col][2];
  59.         int head = 0, tail = 0;
  61.         queue[tail][0] = row;
  62.         queue[tail][1] = col;
  63.         tail++;
  64.         vis_1[row][col] = true;
  65.         count++;
  66.         sum += map[row][col];
  68.         while(head < tail)
  69.         {
  70.             for(int i=0; i<dir.length; i++)
  71.             {
  72.                 int next_row = queue[head][0] + dir[i][0];
  73.                 int next_col = queue[head][1] + dir[i][1];
  75.                 if(next_row>=0 && next_row<Row && next_col>=0 && next_col<Col)
  76.                 {
  77.                     int next_height = map[next_row][next_col];
  79.                     if(next_height <= map[row][col])
  80.                     {
  81.                         if(next_row==0 || next_row==Row-1 || next_col==0 || next_col==Col-1)
  82.                             return 0;
  84.                         if(!vis_1[next_row][next_col])
  85.                         {
  86.                             queue[tail][0] = next_row;
  87.                             queue[tail][1] = next_col;
  88.                             tail++;
  89.                             vis_1[next_row][next_col] = true;
  90.                             count++;
  91.                             sum += map[next_row][next_col];
  92.                         }
  93.                     }
  94.                     else if(next_height < min)
  95.                     {
  96.                         flag = true;
  97.                         min = next_height;
  98.                     }
  99.                 }
  100.             }
  101.             head++;
  102.         }
  104.         if(!flag)
  105.             return 0;
  107.         for(int i=1; i<Row-1; i++)
  108.             for(int j=1; j<Col-1; j++)
  109.                 vis[i][j] = vis_1[i][j];
  111.         return min * count - sum;
  112.     }
  114. }

可见，如果数值不同时两个高度的水平面相邻，会影响水平面划分的结果，可以考虑对内部的点先进行排序，从地势高的的开始划分同一水平面，可以避免上述情况。

Solution_2（暴力+队列）

思路：假设除了边界以外，每个点都存储了最大值。接下来遍历每个点，根据其四周高度最小的点计算该点要溢出的雨水量。
注意：每个点雨水的量改变之后都有可能会影响到其四周的点，所以将改变的点存入队列，然后挨个取出判断其四周的点是否会随之改变。

  1. import java.util.Scanner;
  3. public class rain 
  4. {
  5.     static int T;
  6.     static int Row, Col;
  7.     static int[][] map;        //初始时格子的高度
  8.     static int[][] result_map;    //存储了雨水之后的高度
  10.     static int[][] queue;
  11.     static int tail, head;
  13.     static int[][] dir = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
  14.     static long result;        //存储的雨水量
  16.     public static void main(String[] args) 
  17.     {
  18.         Scanner sc = new Scanner(System.in);
  19.         T = sc.nextInt();
  21.         for(int t=0; t<T; t++)
  22.         {
  23.             Row = sc.nextInt();
  24.             Col = sc.nextInt();
  25.             map = new int[Row][Col];
  26.             result_map = new int[Row][Col];
  27.             result = 0;
  29.             for(int i=0; i<Row; i++)
  30.             {    
  31.                 for(int j=0; j<Col; j++)
  32.                 {
  33.                     map[i][j] = sc.nextInt();
  34.                     if(IsBorder(i, j))
  35.                         result_map[i][j] = map[i][j];
  36.                     else    //假设初始时，每格的雨水全部存到最大值
  37.                     {
  38.                         result_map[i][j] = Integer.MAX_VALUE;
  39.                         result += Integer.MAX_VALUE - map[i][j];
  40.                     }
  41.                 }
  42.             }
  44.             //队列存储更新了高度的点
  45.             queue = new int[Row*Col][2];
  46.             tail = 0;
  47.             head = 0;
  49.             bfs();
  50.             System.out.println(result);
  51.         }
  52.         sc.close();
  53.     }
  55.     //判断该点是否是边界
  56.     private static boolean IsBorder(int row, int col) 
  57.     {
  58.         if(row==0 || row==Row-1 || col==0 || col==Col-1)
  59.             return true;
  60.         return false;
  61.     }
  63.     private static void bfs() 
  64.     {
  65.         //初次更新所有点的高度
  66.         for(int i=1; i<Row-1; i++)
  67.             for(int j=1; j<Col-1; j++)
  68.                 result -= change(i ,j);
  70.         while(head != tail)
  71.         {
  72.             //取出高度改变的点
  73.             int row = queue[head][0];
  74.             int col = queue[head][1];
  76.             //遍历其四周可能产生影响的点
  77.             for(int i=0; i<dir.length; i++)
  78.             {
  79.                 int next_row = row + dir[i][0];
  80.                 int next_col = col + dir[i][1];
  82.                 if(!IsBorder(next_row, next_col))
  83.                     result -= change(next_row, next_col);
  84.             }
  85.             head = (head + 1) % (Row * Col);
  86.         }
  87.     }
  89.     //返回该点流出的雨水量，并把更新的点加入到队列
  90.     private static int change(int row, int col) 
  91.     {
  92.         int flow = FlowCount(row, col);
  93.         if(flow > 0)
  94.         {
  95.             //如果计算出 流出了雨水之后的高度大于原本高度，
  96.             //说明该点低于四周的点，流出的量是根据四周的点计算的
  97.             if(result_map[row][col] - flow > map[row][col])
  98.             {
  99.                 result_map[row][col] -= flow;
  100.                 queue[tail][0] = row;
  101.                 queue[tail][1] = col;
  102.                 tail = (tail + 1) % (Row * Col);
  103.             }
  104.             //否则 说明该点高于四周的点，
  105.             //流出的雨水量只取决于该点本身的高度（初始时假定高度为MAX_VALUE）
  106.             else
  107.             {
  108.                 flow = result_map[row][col] - map[row][col];
  109.                 if(flow > 0)
  110.                 {
  111.                     result_map[row][col] = map[row][col];
  112.                     queue[tail][0] = row;
  113.                     queue[tail][1] = col;
  114.                     tail = (tail + 1) % (Row * Col);
  115.                 }
  116.             }
  117.             return flow;
  118.         }
  119.         return 0;
  120.     }
  122.     //根据四周的点，判断该点要流出的雨水量
  123.     private static int FlowCount(int row, int col) 
  124.     {
  125.         int min = Integer.MAX_VALUE;
  126.         for(int i=0; i<dir.length; i++)
  127.         {
  128.             int next_row = row + dir[i][0];
  129.             int next_col = col + dir[i][1];
  131.             if(result_map[next_row][next_col] < min)
  132.                 min = result_map[next_row][next_col];
  133.         }
  135.         int flow = result_map[row][col] - min;
  136.         return flow>0 ? flow : 0;
  137.     }
  139. }

Solution_3（小根堆+木桶原理）

既然说到桶装水，那么本题显然和水桶原理有点关系：水桶的装水量由最低的那块木板决定
回到本体，显然边界的位置不能装水，那么它们就像是桶边，那么装水量显然和最低的那个位置有关系。也就是，不管内部的容器有多高或者多低，反正放的水的高度都受现在边界的最低高度限制。
那么显然，现在最低边界相邻的那个内部位置高度与边界高度的关系有：

  • 边界高度大于内部位置。这种情况下，无论该位置其它三个方向的相邻高度为多少，该位置都可以放水，容量为 边界高度 - 内部位置高度
  • 边界高度小于等于内部位置。这种情况下，该位置肯定不能放水

然后，不管该位置放水与否，我们都将其视为新的边界：

  • 若它放水了，那么根据水桶原理，它相邻不会再有比当前位置更高的水面，于是它可以想象成一块和水面一样高的木板，也就是边界
  • 若它没放水，肯定是高于原来的边界，就可以想象成一块钉在外部木板的内部木板，一个新边界

接下来，我们继续刚刚的操作，对下一个最低边界做这样的操作
于是可以使用堆存下边界的位置和高度的二元组。并标记放入的位置，防止重复放入
那么，每次都弹出堆顶元素，即还未处理的最低边界，然后进行上述操作，每次形成新边界时都放入堆，对于放入过堆的元素都进行标记

  1. import java.util.Scanner;
  3. public class rain 
  4. {
  5.     static int T;
  6.     static int Row, Col;
  7.     static int[][] map;
  8.     static boolean[][] vis;
  10.     static int[][] dir = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
  11.     static int result;
  13.     public static void main(String[] args) 
  14.     {
  15.         Scanner sc = new Scanner(System.in);
  16.         T = sc.nextInt();
  18.         for(int t=0; t<T; t++)
  19.         {
  20.             Row = sc.nextInt();
  21.             Col = sc.nextInt();
  22.             map = new int[Row][Col];
  23.             vis = new boolean[Row][Col];
  24.             result = 0;
  26.             Heap heap = new Heap(Row * Col);
  28.             for(int i=0; i<Row; i++)
  29.             {    
  30.                 for(int j=0; j<Col; j++)
  31.                 {
  32.                     map[i][j] = sc.nextInt();
  33.                     if (i==0 || i==Row-1 || j==0 || j==Col-1)
  34.                     {
  35.                         vis[i][j] = true;
  36.                         heap.push(i, j, map[i][j]);
  37.                     }
  38.                 }
  39.             }
  40. //            heap.Print();
  41.             while(heap.len > 0)
  42.             {
  43.                 int x = heap.getX(0);
  44.                 int y = heap.getY(0);
  45.                 heap.pop();
  47.                 for(int i=0; i<dir.length; i++)
  48.                 {
  49.                     int next_x = x + dir[i][0];
  50.                     int next_y = y + dir[i][1];
  52.                     if (next_x<=0 || next_x>=Row-1 || next_y<=0 || next_y>=Col-1 || vis[next_x][next_y])
  53.                         continue;
  55.                     int board_height = map[x][y];
  56.                     int now_height = map[next_x][next_y];
  57.                     int inject_rain = board_height - now_height;
  58.                     if(inject_rain > 0)
  59.                     {
  60.                         result += inject_rain;
  61.                         map[next_x][next_y] = board_height;
  62.                         now_height = board_height;
  63.                     }
  64.                     heap.push(next_x, next_y, now_height);
  65.                     vis[next_x][next_y] = true;
  66.                 }
  67.             }
  68.             System.out.println(result);
  69.         }
  70.         sc.close();
  71.     }
  72. }
  74. //小根堆
  75. class Heap
  76. {
  77.     Node[] tree;
  78.     int len;
  80.     //开辟空间
  81.     Heap(int length)
  82.     {
  83.         this.tree = new Node[length];
  84.         this.len = 0;
  85.     }
  87.     //打印堆中元素
  88.     public void Print() 
  89.     {
  90.         for(int i=0; i<len; i++)
  91.             System.out.print(tree[i].x + " ");
  92.         System.out.println();
  94.         for(int i=0; i<len; i++)
  95.             System.out.print(tree[i].y + " ");
  96.         System.out.println();
  98.         for(int i=0; i<len; i++)
  99.             System.out.print(tree[i].height + " ");
  100.         System.out.println();
  101.     }
  103.     //交换堆中两个下标标记的结点内容
  104.     void swap(int index1, int index2)
  105.     {
  106.         Node temp = new Node(tree[index1]);
  107.         tree[index1] = new Node(tree[index2]);
  108.         tree[index2] = temp;
  109.     }
  111.     //index1中结点的值是否比index2中结点的值小
  112.     boolean compare(int index1, int index2)
  113.     {
  114.         if(tree[index1].height < tree[index2].height)
  115.             return true;
  116.         return false;
  117.     }
  119.     //往堆中加入一个元素，并调整堆
  120.     void push(int x, int y, int height)
  121.     {
  122.         tree[len] = new Node(x, y, height);
  123.         int current = len;
  124.         int parent = (current - 1) / 2;
  125.         //从下往上调整，小于父节点的上移
  126.         while(current > 0)
  127.         {
  128.             if(compare(current, parent))
  129.             {
  130.                 swap(current, parent);
  131.                 current = parent;
  132.                 parent = (current - 1) / 2;
  133.             }
  134.             else
  135.                 break;
  136.         }
  137.         len++;
  138.     }
  140.     //由于无法同时返回两个数值，取出堆中最小元素时，调用三个函数体
  141.     int getX(int index)
  142.     {
  143.         return tree[index].x;
  144.     }
  146.     int getY(int index)
  147.     {
  148.         return tree[index].y;
  149.     }
  151.     //取出堆顶元素后，调整堆
  152.     void pop()
  153.     {
  154.         //实现堆顶元素和堆底元素位置交换，并从堆中取出最小值
  155.         len --;
  156.         tree[0] = new Node(tree[len]);
  158.         //从上到下调整堆
  159.         int current = 0;
  160.         int lChild = current * 2 + 1;
  161.         int rChild = current * 2 + 2;
  163.         while(current < len)
  164.         {
  165.             if(lChild >= len)
  166.                 break;
  168.             //记录左右孩子中较小的结点
  169.             int minChild = lChild;    
  170.             if(rChild<len && compare(rChild, minChild))
  171.                 minChild = rChild;
  173.             //交换父子结点位置，把较大的结点挪到下面
  174.             if(compare(minChild, current))
  175.             {
  176.                 swap(minChild, current);
  177.                 current = minChild;
  178.                 lChild = current * 2 + 1;
  179.                 rChild = current * 2 + 2;
  180.             }
  181.             else
  182.                 break;
  183.         }
  184.     }
  185. }
  187. //结点类
  188. class Node
  189. {
  190.     int x;
  191.     int y;
  192.     int height;
  194.     Node() {}
  196.     Node(Node node) 
  197.     {
  198.         this.height = node.height;
  199.         this.x = node.x;
  200.         this.y = node.y;
  201.     }
  203.     Node(int x, int y, int height) 
  204.     {
  205.         this.height = height;
  206.         this.x = x;
  207.         this.y = y;
  208.     }
  209. }

Solution_4（大根堆+BFS，实现Solution_1）

遍历每个未被访问的点，数值小于等于该点的所有点接雨水后可以形成高度相同的水面，同一个水面的高度都是其四周方块最小的值，可以计算出每个水平面需要填补的雨水数量。
但如果数值不同时两个高度的水平面相邻，会影响水平面划分的结果，先使用堆对内部的点进行排序，从地势高的的开始划分同一水平面，可以避免影响水平面的划分。

  1. import java.util.Scanner;
  3. //结点类
  4. class Node
  5. {
  6.     int x;
  7.     int y;
  8.     int height;
  10.     Node() {}
  12.     Node(Node node)
  13.     {
  14.         this.x = node.x;
  15.         this.y = node.y;
  16.         this.height = node.height;
  17.     }
  19.     Node(int x, int y, int height)
  20.     {
  21.         this.x = x;
  22.         this.y = y;
  23.         this.height = height;
  24.     }
  25. }
  27. //大根堆
  28. class Heap
  29. {
  30.     Node[] tree;
  31.     int len;
  33.   //构造函数
  34.     Heap() {}
  36.   //开辟空间
  37.     Heap(int length)
  38.     {
  39.         tree = new Node[length];
  40.         len = 0;
  41.     }
  43.   //打印堆中元素
  44.     public void Print() 
  45.     {
  46.         for(int i=0; i<len; i++)
  47.             System.out.print(tree[i].x + " ");
  48.         System.out.println();
  50.         for(int i=0; i<len; i++)
  51.             System.out.print(tree[i].y + " ");
  52.         System.out.println();
  54.         for(int i=0; i<len; i++)
  55.             System.out.print(tree[i].height + " ");
  56.         System.out.println();
  58.         System.out.println();
  59.     }
  61.   //交换堆中两个下标标记的结点内容
  62.     void swap(int index1, int index2)
  63.     {
  64.         Node temp = new Node(tree[index1]);
  65.         tree[index1] = new Node(tree[index2]);
  66.         tree[index2] = temp;
  67.     }
  69.   //index1中结点的值是否比index2中结点的值大
  70.     boolean compare(int index1, int index2)
  71.     {
  72.         if(tree[index1].height > tree[index2].height)
  73.             return true;
  74.         return false;
  75.     }
  77.   //往堆中加入一个元素，并调整堆
  78.     void push(int x, int y, int height)
  79.     {
  80.         tree[len] = new Node(x, y, height);
  81.         int current = len;
  82.         int parent = (current - 1) / 2;
  83.         //从下往上调整，大于父节点的结点上移
  84.         while(current > 0)
  85.         {
  86.             if(compare(current, parent))
  87.             {
  88.                 swap(current, parent);
  89.                 current = parent;
  90.                 parent = (current - 1) / 2;
  91.             }
  92.             else
  93.                 break;
  94.         }
  95.         len++;
  96.     }
  98.   //由于无法同时返回两个数值，取出堆中最大元素时，需要调用三个函数体
  99.     int getX(int index)
  100.     {
  101.         return tree[index].x;
  102.     }
  104.     int getY(int index)
  105.     {
  106.         return tree[index].y;
  107.     }
  109.   //取出堆顶元素后，调整堆
  110.     void pop()
  111.     {
  112.       //实现堆顶元素和堆底元素位置交换，并从堆中取出最大值
  113.         len--;
  114.         tree[0] = new Node(tree[len]);
  116.       //从上到下调整堆
  117.         int current = 0;
  118.         int lChild = current * 2 + 1;
  119.         int rChild = current * 2 + 2;
  120.         while(lChild < len)
  121.         {
  122.           //记录左右孩子中较小的结点
  123.             int minChild = lChild;
  124.             if(rChild<len && compare(rChild, minChild))
  125.                 minChild = rChild;
  127.           //交换父子结点位置，把较小的结点挪到下面
  128.             if(compare(minChild, current))
  129.             {
  130.                 swap(minChild, current);
  131.                 current = minChild;
  132.                 lChild = current * 2 + 1;
  133.                 rChild = current * 2 + 2;
  134.             }
  135.             else
  136.                 break;
  137.         }
  138.     }
  139. }
  141. public class rain 
  142. {
  143.     static int T;
  144.     static int Row, Col;
  145.     static int[][] map;
  146.     //所有可能存储雨水的格子按高度降序排序
  147.     static Heap heap;
  148.     //已经接了雨水的格子被标为true
  149.     static boolean[][] vis_raw;
  151.     static int[][] dir = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
  153.     static int ans;
  155.     public static void main(String[] args) 
  156.     {
  157.         Scanner sc = new Scanner(System.in);
  158.         T = sc.nextInt();
  160.         for(int t=0; t<T; t++)
  161.         {
  162.             Row = sc.nextInt();
  163.             Col = sc.nextInt();
  164.             map = new int[Row][Col];
  165.             heap = new Heap(Row * Col);
  167.             vis_raw = new boolean[Row][Col];
  169.             ans = 0;
  171.             for(int i=0; i<Row; i++)
  172.             {
  173.                 for(int j=0; j<Col; j++)
  174.                 {
  175.                     map[i][j] = sc.nextInt();
  176.                     if (i==0 || i==Row-1 || j==0 || j==Col-1)
  177.                         continue;
  178.                     //除了边界外的格子全都进入堆
  179.                     heap.push(i, j, map[i][j]);
  180.                 }
  181.             }
  182. //            heap.Print();
  183.             bfs();
  184.             System.out.println(ans);
  185.         }
  186.         sc.close();
  187.     }
  189.     private static void bfs() 
  190.     {
  191.         while(heap.len > 0)
  192.         {
  193.             //由高到低取出堆中还没有存雨水的点
  194.             int row = heap.getX(0);
  195.             int col = heap.getY(0);
  196.             heap.pop();
  198.             if(vis_raw[row][col])
  199.                 continue;
  201.             //水面四周最矮的边界
  202.             int min = Integer.MAX_VALUE;
  203.             int count = 0, sum = 0;    //接雨水的格子个数、底部总共的格子数，用于计算该水面区域接到的雨水
  205.             //拷贝接雨水的区域，如果发现边界太低无法接水，可以免于回溯
  206.             boolean[][] vis = new boolean[Row][Col];
  207.             for(int i=1; i<Row-1; i++)
  208.                 for(int j=0; j<Col-1; j++)
  209.                     vis[i][j] = vis_raw[i][j];
  212.             //bfs核心：将可以归为同一水平面的点入队，并进行宽搜
  213.             int[][] queue = new int[Row * Col][2];
  214.             int head = 0, tail = 0;
  216.             queue[tail][0] = row;
  217.             queue[tail][1] = col;
  218.             tail++;
  219.             vis[row][col] = true;
  220.             count++;
  221.             int cur_height = map[row][col];
  222.             sum += cur_height;
  224.             //如果一个平面到了四周，高度还是低于当前点的高度，说明接不住雨水
  225.             boolean leak = false;
  226.             while(head<tail && !leak)
  227.             {
  228.                 for(int i=0; i<dir.length; i++)
  229.                 {
  230.                     int next_row = queue[head][0] + dir[i][0];
  231.                     int next_col = queue[head][1] + dir[i][1];
  233.                     //因为加入队列中的点都不是边界，所以不会有数组越界的情况，无需判断
  235.                     int next_height = map[next_row][next_col];
  236.                     //该点四周的点地势比当前点更低，存在两种情况：
  237.                     //1. 四周的点位于边缘，该区域无法接水，会漏
  238.                     //2. 四周的点不在边缘，也是同一水平面的点，加入队列
  239.                     if(next_height <= cur_height)
  240.                     {
  241.                         if(next_row==0 || next_row==Row-1 || next_col==0 || next_col==Col-1)
  242.                         {
  243.                             leak = true;
  244.                             break;
  245.                         }
  246.                         if(!vis[next_row][next_col])
  247.                         {
  248.                             queue[tail][0] = next_row;
  249.                             queue[tail][1] = next_col;
  250.                             tail++;
  251.                             vis[next_row][next_col] = true;
  252.                             count++;
  253.                             sum += next_height;
  254.                         }
  255.                     }
  256.                     //该点四周的点地势比当前点更高，判断是否可以更新边界的最小值
  257.                     else if(next_height < min)
  258.                         min = next_height;
  259.                 }
  260.                 head++;
  261.             }
  263.             //可以接水
  264.             if(!leak)
  265.             {
  266.                 //把当前已经接雨水的点更新到全局
  267.                 for(int i=1; i<Row-1; i++)
  268.                     for(int j=1; j<Col-1; j++)
  269.                         vis_raw[i][j] = vis[i][j];
  271.                 //计算当前水平面接到的雨水，更新到结果
  272.                 int rain = min * count - sum;
  273.                 ans += rain;
  274.             }
  276.         }
  277.     }
  279. }