题面

https://www.luogu.com.cn/problem/P1363

题解

先说正解。

怎么样才能判断可以无限延伸呢？那就是如果存在一条路径

$$
P \rightsquigarrow P'
$$

其中 $P'$ 为任意一个虚幻棋盘中 $P$ 的对应点。

证明十分容易。

充分性证明：记坐标 $P$ 为 $P(x, y), 0 \leq x < n, 0 \leq y < m$。那么：

$$
P'(x + na, y + mb), a, b \in \mathbb Z, a,b 不同时为0
$$

所以根据假设存在下面的路径：

$$
P(x, y) \rightsquigarrow P(x + na, y + mb)
$$

则亦存在：

$$
P(x + na, y + mb) \rightsquigarrow P(x + 2na, y + 2mb)
$$

我们将路径记作下面这种映射：

$$
f(x, y) = (x + na, y + mb)
$$

故我们可以不断应用：

$$
f^{(t)}(x, y) = \underbrace{f(f(\cdots f}_{t}(x, y) \cdots)) = (x + tna, y + tmb)
$$

故

$$
\lim_{t \rightarrow \infty} f^{(t)}(x, y) = \begin{cases}
(\infty, \infty) & ab \neq 0 \\ (0, \infty) & a = 0 \\ (\infty, 0) & b = 0
\end{cases}
$$

必要性证明可以通过反证法证得：

向无穷远处延伸代表存在长度为无穷的路径。接下来应用反正：若存在长度为无穷的路径，且不存在形如题设的 $P \rightsquigarrow P'$ 的路径。

若不存在形如 $P \rightsquigarrow P'$ 的路径，那么路径长度必然是有限的，因为我们能够构造出来的路径都形如下式：

$$
S \rightsquigarrow T = S \rightsquigarrow A_1 \rightsquigarrow A_2 \rightsquigarrow \cdots \rightsquigarrow A_p \rightsquigarrow T
$$

其中等式右侧的每条路径都不存在中间点。我们不难发现集合 $A$ 是有限的，因为原棋盘是有限的，故 $|A \cup \{S, T\}| \leq nm$。故长度必然为有限，与长度为无限矛盾。证毕。

下面是一些错误结论：

错误结论 1：向上下左右各拓展一个棋盘，如果一个点被等价走到了两次，那么就可以到达无穷。

反例：

代码

#include <iostream>
#include <cstring>

using namespace std;

const int maxn = 1505;

const int dx[4] = {-1, 0, 0, 1};
const int dy[4] = {0, -1, 1, 0};

int n, m, sx, sy, vx[maxn][maxn], vy[maxn][maxn];
bool map[maxn][maxn], vis[maxn][maxn], ans;

void dfs(int x, int y, int lx, int ly) {
    if (ans) return;
    if (vis[x][y]) {
        if (vx[x][y] != lx || vy[x][y] != ly) ans = 1;
        return;
    }

    vis[x][y] = 1; vx[x][y] = lx; vy[x][y] = ly;

    for (int i = 0; i < 4; i ++) {
        int xx = (x + n + dx[i]) % n; 
        int yy = (y + m + dy[i]) % m;
        int lxx = lx + dx[i], lyy = ly + dy[i];
        if (map[xx][yy])
            dfs(xx, yy, lxx, lyy);
    }
}

int main() {
    char in;
    while (cin >> n >> m) {
        for (int i = 0; i < n; i ++)
            for (int j = 0; j < m; j ++) {
                cin >> in;
                map[i][j] = (in != '#');
                if (in == 'S') sx = i, sy = j;
            }
        memset(vis, 0, sizeof(vis));
        memset(vx, 0, sizeof(vx));
        memset(vy, 0, sizeof(vy));
        ans = 0;

        dfs(sx, sy, sx, sy);

        if (ans) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}
最后修改：2022 年 04 月 09 日 09 : 55 PM
© 允许规范转载
真的不买杯奶茶嘛....qwq