正经题解｜水流问题

【算法分析】

可以考虑从大西洋和太平洋开始搜索。从大西洋开始搜索可以相当于从与大西洋相邻的位置开始搜索，搜索的规则就是当前位置的值小于等于搜索位置的值。用一个数组存储有这个位置可以流到海洋的数目，因此当搜索到一个位置的时候需要将这个数组的值加一，从太平洋也是类似的。

【参考代码】

#include<bits/stdc++.h>
using namespace std;

int a[1009][1009], heights[1009][1009];
struct node {
    int x, y;
}l,r;
int dir[4][2] = { -1,0,0,1,1,0,0,-1 };
bool vis[1009][1009];
int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) cin >> heights[i][j];
	}
    queue<node> q;
    for (int i = 0; i < n; i++) q.push({ i,0 }), vis[i][0] = 1;
    for (int j = 1; j < m; j++) q.push({ 0,j }), vis[0][j] = 1;
    while (q.size()) {
        r = q.front();
        q.pop();
        a[r.x][r.y]++;
        for (int i = 0; i < 4; i++) {
            l.x = r.x + dir[i][0], l.y = r.y + dir[i][1];
            if (l.x >= 0 && l.x < n && l.y >= 0 && l.y < m && heights[l.x][l.y] >= heights[r.x][r.y] && !vis[l.x][l.y]) {
                q.push(l);
                vis[l.x][l.y] = 1;
            }
        }
    }

    memset(vis, 0, sizeof(vis));
    for (int i = 0; i < n; i++) q.push({ i,m - 1 }), vis[i][m - 1] = 1;
    for (int j = 0; j < m - 1; j++) q.push({ n - 1,j }), vis[n - 1][j] = 1;
    while (q.size()) {
        r = q.front();
        q.pop();
        a[r.x][r.y]++;
        for (int i = 0; i < 4; i++) {
            l.x = r.x + dir[i][0], l.y = r.y + dir[i][1];
            if (l.x >= 0 && l.x < n && l.y >= 0 && l.y < m && heights[l.x][l.y] >= heights[r.x][r.y] && !vis[l.x][l.y]) {
                q.push(l);
                vis[l.x][l.y] = 1;
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i][j] == 2) {
                ans++;
            }
        }
    }
    cout << ans;
	return 0;
}

【时间复杂度】

$O(n*m)$

【预计得分】

$100pts$