《算法競賽·快沖300題》將于2024年出版，是《算法競賽》的輔助練習冊。
所有題目放在自建的OJ New Online Judge。
用C/C++、Java、Python三種語言給出代碼，以中低檔題為主，適合入門、進階。

“ 造電梯” ，鏈接： http://oj.ecustacm.cn/problem.php?id=1790

題目描述

【題目描述】 現(xiàn)在給你一張建筑的平面圖，按照要求，建筑的每一個部分都應該是輪椅使用者可以到達的，這意味著必須安裝電梯。
?? 給定的平面圖是一個n*m的矩陣，里面的數(shù)字表示這個位置的高度?？梢栽诮ㄖ械娜我馕恢梅胖秒娞?#xff0c;電梯可以停在所有樓層。
?? 需要保證可以使用電梯到達所有高樓層。相同高度的樓層之間是互通的，聯(lián)通準則是四聯(lián)通。
?? 需要求解最少需要多少個電梯，注意高度為1的不需要電梯。
?? 下圖展示了樣例2的可視化三維圖。

【輸入格式】 輸入第一行為n和m(1≤n,m≤500)。
?? 接下來n行，每行m個整數(shù)xij，表示平面圖，0≤xij≤10^9。
【輸出格式】 輸出最少電梯數(shù)量
【輸入樣例】

樣例1：
2 3
1 2 3
1 3 2樣例2：
6 7
0 0 0 0 0 0 0
0 1 2 3 2 1 0
0 1 2 3 2 1 0
0 0 0 0 0 0 0
0 1 0 5 0 0 0
0 0 0 0 0 0 0

【輸出樣例】

樣例1：
2樣例2：
2

---

題解

?? 電梯是裝在建筑內(nèi)部的，例如樣例2，高度5的柱子內(nèi)部需要一個電梯，樓梯狀的建筑也需要一個電梯。
?? 注意一個建筑內(nèi)部可能需要不止一個電梯，例如平面上一個建筑的高度是{5, 2, 4}，那么需要在5和4上建2個電梯。
?? 本題是“洪水填充（《算法競賽》清華大學出版社，羅勇軍，郭衛(wèi)斌著，120頁，3.3 洪水填充）”的應用：從最高處開始倒水，那么水會平流或者往下流，這相當于建了一部電梯；這次倒水沒有流到的地方，繼續(xù)從下一個最高處倒水…
?? 以樣例2為例：
?? （1）從最高的“5”開始倒水，水會平流或往下流，那么會繼續(xù)淹沒所有的“0”。這次倒水相當于建設了一部電梯。沒有被這次倒水淹沒的有第二行和第三行的“1 2 3 2 1”，還有倒數(shù)第二行的“1”。
?? （2）繼續(xù)從剩下的最高點“3”開始倒水，水會平流或往下流，那么第二行和第三行的“1 2 3 2 1”，還有所有的“0”都會淹沒。這次倒水也相當于建設了一部電梯。沒有被這次倒水淹沒的有倒數(shù)第二行的“1”，不過它不需要建設電梯。
?? “洪水填充”用BFS或DFS都行，下面的代碼用BFS實現(xiàn)。把平面的所有點放進優(yōu)先隊列，然后依次取出隊列中的最高點，并從它開始“洪水填充”。
【重點】 洪水填充。

C++代碼

?? 代碼的計算復雜度，設平面上共n個點，每個點只需要處理一次，優(yōu)先隊列進出一次是O(logn)的，所以總復雜度O(nlogn)。

#include <bits/stdc++.h>
using namespace std;
int dx[4] = { 1, 0, -1, 0 };  //上下左右
int dy[4] = { 0, 1, 0, -1 };
struct Point {int x, y, h;                     //坐標xy、高度hPoint(int x_, int y_, int h_) { x = x_; y = y_; h = h_; };bool operator<(const Point& r) const { return (h < r.h); }
};
int n, m;
int a[505][505];
bool done[505][505];  //done[x][y]=1表示(x,y)已經(jīng)淹沒
void floodfill(int x, int y) {      //“洪水填充”，平流或往下流done[x][y] = true;              //標記為淹沒for (int i = 0; i < 4; i++) {    //擴散周圍與它等高或矮的點int nx = x + dx[i], ny = y + dy[i];if (nx < 0 || nx >= m || ny < 0 || ny >= n || done[nx][ny]) continue;if (a[nx][ny] <= a[x][y])floodfill(nx, ny);   //繼續(xù)“洪水填充”}
}
int main() {cin >> n >> m;priority_queue<Point> Q;   //優(yōu)先隊列，隊首的h最大for (int j = 0; j < n; j++)for (int i = 0; i < m; i++) {cin >> a[i][j];done[i][j] = (a[i][j] <= 1);        //0和1標記為已經(jīng)淹沒if(a[i][j] > 1)Q.push(Point(i, j, a[i][j]));   //把點放進優(yōu)先隊列}int ans = 0;while (!Q.empty()) {Point p = Q.top();      //每次取出剩下的最高點Q.pop();if (!done[p.x][p.y]) {  //如果它沒有淹沒過，就“洪水填充”ans++;              //這次倒水相當于建設了一部電梯floodfill(p.x, p.y); //“洪水填充”}}cout << ans << endl;return 0;
}

Java代碼

import java.util.*;
class Point implements Comparable<Point> {int x, y, h;public Point(int x_, int y_, int h_) {x = x_;y = y_;h = h_;}public int compareTo(Point r) { return Integer.compare(-h, -r.h);  }
}public class Main {static int[] dx = { 1, 0, -1, 0 };static int[] dy = { 0, 1, 0, -1 };static int n, m;static int[][] a;static boolean[][] done;public static void floodfill(int x, int y) {done[x][y] = true;for (int i = 0; i < 4; i++) {int nx = x + dx[i], ny = y + dy[i];if (nx < 0 || nx >= m || ny < 0 || ny >= n || done[nx][ny])continue;if (a[nx][ny] <= a[x][y])floodfill(nx, ny);}}public static void floodfill_bfs(int sx, int sy) {Queue<int[]> queue = new LinkedList<>();queue.add(new int[] { sx, sy });done[sx][sy] = true;while (!queue.isEmpty()) {int[] curr = queue.poll();int x = curr[0];int y = curr[1];for (int i = 0; i < 4; i++) {int nx = x + dx[i], ny = y + dy[i];if (nx >= 0 && nx < m && ny >= 0 && ny < n && !done[nx][ny] && a[nx][ny] <= a[x][y]) {queue.add(new int[] { nx, ny });done[nx][ny] = true;}}}}public static void main(String[] args) {Scanner input = new Scanner(System.in);n = input.nextInt();m = input.nextInt();a = new int[m][n];done = new boolean[m][n];PriorityQueue<Point> Q = new PriorityQueue<>();for (int j = 0; j < n; j++) {for (int i = 0; i < m; i++) {a[i][j] = input.nextInt();done[i][j] = (a[i][j] <= 1);if (a[i][j] > 1)    Q.add(new Point(i, j, a[i][j]));}}int ans = 0;while (!Q.isEmpty()) {Point p = Q.poll();if (!done[p.x][p.y]) {ans++;floodfill_bfs(p.x, p.y);}}System.out.println(ans);input.close();}
}

Python代碼

from collections import deque
import heapq
import sys
input = sys.stdin.readlinedx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
n, m = map(int, input().split())
a = [[0] * n for _ in range(m)]
done = [[False] * n for _ in range(m)]Q = []
for j in range(n):row_a = list(map(int, input().split()))for i in range(m):a[i][j] = row_a[i]if a[i][j] <= 1:  done[i][j]=Trueelse:             heapq.heappush(Q, (-a[i][j], i, j)) 
ans = 0 
while Q:_, sx, sy = heapq.heappop(Q)if not done[sx][sy]:ans += 1q = deque([(sx, sy)])done[sx][sy] = True while q:x, y = q.popleft()for i in range(4):nx, ny = x + dx[i], y + dy[i]if 0 <= nx < m and 0 <= ny < n and not done[nx][ny] and a[nx][ny] <= a[x][y]:q.append((nx, ny))done[nx][ny] = True
print(ans)