题目内容某个建筑工地上堆放着很多防水建材它们每一块的规格都一模一样但是每一叠都高矮不一这些建材堆放得非常整齐而且非常紧凑紧凑到 “滴水不漏”。建材一共有nnn行mmm列。现在给你一个$ n×m$ 的矩阵第$ n行第行第行第m $列上的数字表示对应位置建材的数量。例如下面的矩阵所示第 $1行第行第行第1$ 列的 “222” 表示这个位置对应的那一叠建材的数量为$ 2$ 块。特别地最旁边的建材是没有办法形成水坑的。某天突然天降暴雨暴雨过后在建材区形成了很多个小水坑。如果某一叠建材的数量比它周围上、下、左、右的建材数量少将形成一个小水坑。相邻的两叠或者多叠建材可能会构成一个大一点的水坑。例如在上面的图中两叠红色的建材将构成一个水坑因为它们周围上、下、左、右的建材蓝色建材的数量比它们要多。假如这场雨下得足够大足以让每一个水坑都装满水。现在请问暴雨过后在建材区一共留下了多少个水坑输入描述第111行输入两个正整数分别表示$ n$ 和mmmnnn和$ m$ 均不超过100100100两个数字之间用空格隔开。接下来$ n$ 行每行一个$ m$ 的矩阵每一行$ m $个正整数表示某一叠建材的数量两个正整数之间用空格隔开。输出描述输出一个整数即留下的水坑数量存在一个水坑也没有的情况样例1输入4 4 2 3 5 1 4 1 2 3 1 5 4 2 1 2 2 2输出1解题思路把每个位置看成一个高度为h[i][j]h[i][j]h[i][j]的格子。一个位置如果想把水排到边界一定存在一条从它走到边界的路径并且沿途高度不能升高。因为水只会从高处流向低处或者同高度的位置。所以我们可以反过来想从边界开始做一次搜索如果当前在位置(x,y)(x,y)(x,y)那么可以走到相邻位置(nx,ny)(nx,ny)(nx,ny)当且仅当h[nx][ny]≥h[x][y]h[nx][ny] \ge h[x][y]h[nx][ny]≥h[x][y]原因是如果反向能这样走过去就说明正向时那个位置的水可以沿着“不升高”的路径流到边界因此它不可能属于水坑。算法分两步从所有边界格子出发做一次BFS/DFSBFS/DFSBFS/DFS标记所有“能够漏到边界”的位置搜索规则是只走向高度大于等于当前格子的相邻位置。所有没有被标记的位置都是“无法漏到边界”的位置。这些位置按上下左右连通块划分每一个连通块就是一个水坑。再做一次BFS/DFSBFS/DFSBFS/DFS统计连通块个数即可。核心算法是反向搜索连通块统计BFS/DFSBFS/DFSBFS/DFS这样做的关键好处是不需要真的模拟装水过程只需要判断一个位置能不能“漏出去”。复杂度分析设矩阵大小为n×mn \times mn×m。第一次从边界反向搜索每个格子最多进队一次时间复杂度为O(nm)O(nm)O(nm)第二次统计剩余格子的连通块每个格子也最多访问一次时间复杂度为O(nm)O(nm)O(nm)所以总时间复杂度为O(nm)O(nm)O(nm)额外使用了访问数组和队列空间复杂度为O(nm)O(nm)O(nm)在题目给出的数据范围下是完全可行的。代码实现Pythonfromcollectionsimportdequeimportsys# 统计水坑数量defcount_pits(grid,n,m):vis[[False]*mfor_inrange(n)]qdeque()dirs[(-1,0),(1,0),(0,-1),(0,1)]# 先把所有边界点加入队列foriinrange(n):ifnotvis[i][0]:vis[i][0]Trueq.append((i,0))ifm1andnotvis[i][m-1]:vis[i][m-1]Trueq.append((i,m-1))forjinrange(m):ifnotvis[0][j]:vis[0][j]Trueq.append((0,j))ifn1andnotvis[n-1][j]:vis[n-1][j]Trueq.append((n-1,j))# 反向搜索从低处可以走到高处或等高处# 说明这些位置的水能沿不升高路径流到边界whileq:x,yq.popleft()fordx,dyindirs:nx,nyxdx,ydyif0nxnand0nym:ifnotvis[nx][ny]andgrid[nx][ny]grid[x][y]:vis[nx][ny]Trueq.append((nx,ny))# 统计所有未被标记位置的连通块数量ans0foriinrange(n):forjinrange(m):ifnotvis[i][j]:ans1vis[i][j]Trueq.append((i,j))whileq:x,yq.popleft()fordx,dyindirs:nx,nyxdx,ydyif0nxnand0nymandnotvis[nx][ny]:vis[nx][ny]Trueq.append((nx,ny))returnansdefmain():datasys.stdin.read().strip().split()ifnotdata:returnnint(data[0])mint(data[1])grid[]idx2for_inrange(n):rowlist(map(int,data[idx:idxm]))grid.append(row)idxmprint(count_pits(grid,n,m))if__name____main__:main()Javaimportjava.util.LinkedList;importjava.util.Queue;importjava.util.Scanner;publicclassMain{// 方向数组上、下、左、右staticint[]dx{-1,1,0,0};staticint[]dy{0,0,-1,1};// 统计水坑数量publicstaticintcountPits(int[][]grid,intn,intm){boolean[][]visnewboolean[n][m];Queueint[]queuenewLinkedList();// 所有边界点入队for(inti0;in;i){if(!vis[i][0]){vis[i][0]true;queue.offer(newint[]{i,0});}if(m1!vis[i][m-1]){vis[i][m-1]true;queue.offer(newint[]{i,m-1});}}for(intj0;jm;j){if(!vis[0][j]){vis[0][j]true;queue.offer(newint[]{0,j});}if(n1!vis[n-1][j]){vis[n-1][j]true;queue.offer(newint[]{n-1,j});}}// 反向搜索当前点可以扩展到更高或等高的位置while(!queue.isEmpty()){int[]curqueue.poll();intxcur[0];intycur[1];for(intk0;k4;k){intnxxdx[k];intnyydy[k];if(nx0nxnny0nym){if(!vis[nx][ny]grid[nx][ny]grid[x][y]){vis[nx][ny]true;queue.offer(newint[]{nx,ny});}}}}// 统计未被标记区域的连通块个数intans0;for(inti0;in;i){for(intj0;jm;j){if(!vis[i][j]){ans;vis[i][j]true;queue.offer(newint[]{i,j});while(!queue.isEmpty()){int[]curqueue.poll();intxcur[0];intycur[1];for(intk0;k4;k){intnxxdx[k];intnyydy[k];if(nx0nxnny0nym!vis[nx][ny]){vis[nx][ny]true;queue.offer(newint[]{nx,ny});}}}}}}returnans;}publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);intnsc.nextInt();intmsc.nextInt();int[][]gridnewint[n][m];for(inti0;in;i){for(intj0;jm;j){grid[i][j]sc.nextInt();}}System.out.println(countPits(grid,n,m));sc.close();}}C#includeiostream#includevector#includequeueusingnamespacestd;// 统计水坑数量intcountPits(constvectorvectorintgrid,intn,intm){vectorvectorboolvis(n,vectorbool(m,false));queuepairint,intq;intdx[4]{-1,1,0,0};intdy[4]{0,0,-1,1};// 所有边界点入队for(inti0;in;i){if(!vis[i][0]){vis[i][0]true;q.push({i,0});}if(m1!vis[i][m-1]){vis[i][m-1]true;q.push({i,m-1});}}for(intj0;jm;j){if(!vis[0][j]){vis[0][j]true;q.push({0,j});}if(n1!vis[n-1][j]){vis[n-1][j]true;q.push({n-1,j});}}// 反向搜索从边界出发走向更高或等高的位置while(!q.empty()){pairint,intcurq.front();q.pop();intxcur.first;intycur.second;for(intk0;k4;k){intnxxdx[k];intnyydy[k];if(nx0nxnny0nym){if(!vis[nx][ny]grid[nx][ny]grid[x][y]){vis[nx][ny]true;q.push({nx,ny});}}}}// 统计剩余未访问格子的连通块数量intans0;for(inti0;in;i){for(intj0;jm;j){if(!vis[i][j]){ans;vis[i][j]true;q.push({i,j});while(!q.empty()){pairint,intcurq.front();q.pop();intxcur.first;intycur.second;for(intk0;k4;k){intnxxdx[k];intnyydy[k];if(nx0nxnny0nym!vis[nx][ny]){vis[nx][ny]true;q.push({nx,ny});}}}}}}returnans;}intmain(){intn,m;cinnm;vectorvectorintgrid(n,vectorint(m));for(inti0;in;i){for(intj0;jm;j){cingrid[i][j];}}coutcountPits(grid,n,m)\n;return0;}