题解：P9698 [GDCPC 2023] Path Planning

· · 题解

提供一个 O(n \times m) 的做法。

因为题目保证了 n \times m 的矩阵内的数字是 0 \sim n \times m−1 每个数字各出现一次，一个比较直观的想法是如果最终确定了路径 S 的 mex(S) = x，那么一定要保证 0 \sim x−1 这 x 个数字要能够同时存在在某条从 (1, 1) 到 (n, m) 的合法路径上。如果我们在对从 0 \sim n \times m − 1 的每个数字的检测途中发现某个数字 y 无法和已经可以同时存在在某条从 (1, 1) 到 (n, m) 的合法路径的数字集合 \{0,1,\dots,y−1\} 共存，即加入 y 这个数字之后就无法构成合法路径，这个时候最后的答案就一定是 y 这个数字。通过上述的分析，现在的问题就可以转变成我们怎么快速判断每个点是否可以合法的加入到集合中。

这个判断并不困难。对于某个数字 num , 其对应的坐标为 (x, y) ，假设它被我们选中了，在选中它之后会存在两个矩形面积区域的点和 num 无法共存，一个是以 (x−1, y+1) 和 (1, m) 这两个点为对角线构成的位于 num 右上方的矩形，另一个是以 (x+1, y −1) 和 (n, 1) 这两个点为对角线构成的位于 num 左下方的矩形，这个结论大家手动模拟一下就能验证。

我们不可能暴力的对每个点对应的这两个矩形内的所有点都做一遍标记，这里介绍一个可以优化的思路：以右上方的矩形为例，这个矩形的起点是 (x−1,y+1)，这个矩形内其它的所有点都位于它的右上方，基于此我们可以采用利用方向向量进行搜索标记的思路，以 (x−1,y+1) 为起点，方向向量采用 (−1, 0) 和 (0, 1) 进行搜索标记，如果发现某些点已经被标记就可以不继续扩张，这样就保证了矩形内每个点至多被标记一次，复杂度为 O(n \times m)。

参考代码如下。

#include <bits/stdc++.h>
#define ll long long
#define mod 1000000007
#define eps 1e−7
using namespace std;

const double PI = acos(−1);
const int N = 1e6 + 10;

int dx[] = {0, 1, 0, −1};
int dy[] = {−1, 0, 1, 0};
int n, m;

void dfs1(int x, int y, vector<vector<int>> &vis)
{
    if (x < 1 || x > n || y < 1 || y > m)
        return;
    vis[x][y] = true;
    for (int i = 2; i <= 3; i++)
    {
        int tx = x + dx[i], ty = y + dy[i];
        if (tx < 1 || ty < 1 || tx > n || ty > m || vis[tx][ty])
            continue;
        dfs1(tx, ty, vis);
    }
}

void dfs2(int x, int y, vector<vector<int>> &vis)
{
    if (x < 1 || x > n || y < 1 || y > m)
        return;
    vis[x][y] = true;
    for (int i = 0; i <= 1; i++)
    {
        int tx = x + dx[i], ty = y + dy[i];
        if (tx < 1 || ty < 1 || tx > n || ty > m || vis[tx][ty])
            continue;
        dfs2(tx, ty, vis);
    }
}

void solve()
{
    cin >> n >> m;

    vector a(n + 10, vector<int>(m + 10, 0));
    vector vis = a;
    vector<pair<int, int>> c((n + 10) * (m + 10));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j], c[a[i][j]] = {i, j};

    int res = 0;
    for (int i = 0; i < n * m; i++)
    {
        if (!vis[c[i].first][c[i].second])
        {
            res++;
            auto [x, y] = c[i];
            vis[x][y] = true;
            dfs1(x − 1, y + 1, vis);
            dfs2(x + 1, y − 1, vis);
        }
        else
            break;
    }
    cout << res << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int _ = 1;
    cin >> _;
    while (_−−)
    {
        solve();
    }

    return 0;
}
/*
 */