<---大佬们点个赞吧qwq

$$\huge\color{orange}{→→→暑假每日一题2022题解合集←←←}$$
$\ $
$\ $

题目描述

Vincenzo 决定制作立方体 IV，但所有预算只够制作一个正方形迷宫。

它是一个完美的迷宫，每个房间都呈正方形，并具有 $4$ 扇门（四个边一边 $1$ 个）。

每个房间里都有一个号码。

一个人只有在下一个房间的号码比当前房间的号码大 $1$ 的情况下，才能从当前房间移动到下一个房间。

现在，Vincenzo 为所有房间分配了唯一的号码（$1,2,3,… S^2$）然后将 $S^2$ 个人放在了迷宫中，每个房间 $1$ 个，其中 $S$ 是迷宫的边长。

能够移动次数最多的人将获胜。

弄清楚谁将成为赢家，以及他将能够到达的房间数量。

输入格式

第一行包含整数 $T$，表示共有 $T$ 组测试数据。

每组测试数据第一行包含整数 $S$，表示迷宫的边长。

接下来 $S$ 行，每行包含 $S$ 个整数，表示具体的迷宫的房间号分布，需注意 $1,2,3,… S^2$ 这 $S^2$ 个数字，每个数字只出现一次。

输出格式

每组数据输出一个结果，每个结果占一行。

结果表示为 Case #x: r d，其中 $x$ 是组别编号（从 $1$ 开始），$r$ 是获胜的人最初所在房间的房间号，$d$ 是他可以到达的房间数量。

如果有多个人可到达的房间数相同，那么最初所在房间的房间号最小的人将获胜。

数据范围

$1 \le T \le 100$,
$1 \le S \le 1000$

输入样例：

2
2
3 4
1 2


3
1 2 9 
5 3 8 
4 6 7

输出样例：

Case #1: 1 2
Case #2: 6 4

算法

(e……bzd) $O(n^2)$（假设 $n$ 是迷宫的边长）

看到这个题最直接的想法就是暴力枚举每一个房间所能到达的房间数，但是这个算法的时间复杂度最坏情况下会达到 $O(n^4)$，不现实。

接下来考虑怎么优化这个算法：

可以发现，只要 $a$ 房间能被另外一个房间 $b$ 走到，那这房间就一定不是最优的（因为 $b$ 能到达的房间数会比 $a$ 能到达的房间数多一个），所以我们只需要枚举不能被其他房间走到的房间。

可以肯定的是，$1$ 号房间肯定不能被其他房间走到，我们可以从 $1$ 号房间开始枚举，一直枚举到不能再走了，然后就能知道 $1$ 号房间所能到达的房间数了。这时我们可以发现，我们又找到了一个不能被其他房间走到的房间！只需要一直这样枚举下去，就能知道最终的答案了。（当然，你也可以不边算边找，可以先枚举所有的房间，把所有不能被其他房间走到的房间找出来，然后再一一枚举。）

时间复杂度

因为每个房间最多遍历 $1$ 次，所以这个算法的时间复杂度就是 $O(n^2)$。

空间复杂度

我们需要记录每个房间的信息，而房间数是 $O(n^2)$，所以这个算法的空间复杂度也是 $O(n^2)$。

C++ 代码（对了，突然觉得以前自己的注释好多都是多余的，所以现在把我认为多余的去掉了，如果有疑问可以打在评论区里）

#include <iostream>

using namespace std;

typedef pair<int, int> PII;

const int N = 1010;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}; // dx, dy: 偏移量数组

int t, n;
int g[N][N]; // g: 迷宫
PII pos[N * N]; // pos[i]: 编号为i的房间的位置（{x, y}）

int main()
{
    cin >> t;
    for (int c = 1; c <= t; c ++ ) // c: 组别编号
    {
        cin >> n;
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < n; j ++ )
                cin >> g[i][j], pos[g[i][j]] = {i, j}; // 读入迷宫，录入位置

        int i = 1, maxv = 0, idx; // i: 要枚举的房间编号, maxv: 获胜房间可以到达的房间数量, idx: 获胜房间的编号
        for (; i <= n * n; )
        {
            int tmp = i; // 记录一下原先的i
            while (i <= n * n)
            {
                bool flag = false; // flag: 是否能走到下一个格子
                int x = pos[i].first, y = pos[i].second; // 这一个房间的位置
                for (int d = 0; d < 4; d ++ )
                {
                    int a = x + dx[d], b = y + dy[d]; // a, b: 下一个房间的位置
                    if (a < 0 || a >= n || b < 0 || b >= n) continue; // 判断越界
                    if (g[a][b] == g[x][y] + 1)
                    {
                        flag = true;
                        break;
                    }
                }

                i ++ ;
                if (!flag) break;
            }

            if (maxv < i - tmp) maxv = i - tmp, idx = tmp; // i - tmp是可以到达的房间数量，用这个去更新答案
        }

        printf("Case #%d: %d %d\n", c, idx, maxv);
    }

    return 0;
}