有一个无穷大的迷宫，每个方格是空地或障碍，保证这个迷宫在行上以 $n$ 为周期，在列上以 $m$ 为周期。
形式化地，设 $\left( r, c \right)$ 表示第 $r$ 行第 $c$ 列的方格，则对于 $r, c \in \mathbb Z$，则 $\left( r, c \right)$ 为障碍当且仅当 $\left( r \bmod n, c \bmod m \right)$ 为障碍 (这里 $\bmod$ 运算默认返回非负数)。
你需要从原点 $\left( 0, 0 \right)$ 开始 (保证 $\left( 0, 0 \right)$ 不是障碍)，每次向四个方向移动一格，不能经过障碍。
给定 $q$ 组询问，每次询问给出 $\left( r_i, c_i \right)$，你需要回答你是否能到达 $\left( r_i, c_i \right)$。
第一行包含两个正整数 $n, m$ ($n, m \leq 100$)，表示迷宫的行数和列数。
接下来 $n$ 行，每行一个长度为 $m$ 的，由 # 和 . 构成的字符串，其中第 $i$ 行的第 $j$ 个字符为 # 当且仅当 $\left( i - 1, j - 1 \right)$ 是障碍。保证 $\left( 0, 0 \right)$ 不是障碍。
第 $n + 2$ 行包含一个正整数 $q$ ($q \leq 2 \times 10^5$)，表示询问的组数。
最后 $q$ 行，每行两个整数 $r_i, c_i$ ($-10^9 \leq r_i, c_i \leq 10^9$)，表示询问 $\left( r_i, c_i \right)$ 是否能到达。保证 $\left( r_i, c_i \right)$ 不是障碍。
对于每组询问，输出一行，如果能从 $\left( 0, 0 \right)$ 到达 $\left( r_i, c_i \right)$ 则为 yes，否则为 no。
对于一个方格 $\left( r, c \right)$，存在唯一的 $\left( r_B, c_B \right)$ 满足 $r = n \cdot r_B + r_T, c = m \cdot c_B + c_T$，且 $0 \leq r_T < n, 0 \leq c_T < m$。
我们记 $\left( r_B, c_B \right)$ 为 $\left( r, c \right)$ 的块坐标，$\left( r_T, c_T \right)$ 为 $\left( r, c \right)$ 的余坐标。
考虑所有余坐标为 $\left( 0, 0 \right)$ 的点的集合，设其中和 $\left( 0, 0 \right)$ $4-$连通的点 (即答案为 yes 的点) 的块坐标集合为 $V$。显然 $\left( 0, 0 \right) \in V$。
则 $V$ 是一个 $\mathbb Z^2$ 上的格 (Lattice) (即满足对 $\boldsymbol a, \boldsymbol b \in V$ 和 $\lambda, \mu \in \mathbb Z$，总有 $\lambda \boldsymbol a + \mu \boldsymbol b \in V$ 的集合)。
$\mathbb Z^2$ 上的格还是有点乱，因为它可能会包含各种这样的集合。但是下面即将证明的介值性质会大大减少这种满足条件的格的数量。
定理 (介值性质)：设整数向量 $\boldsymbol a, \boldsymbol b \in \mathbb Z^2$，$k \in \mathbb N^*$。若 $\boldsymbol a \in V, \boldsymbol a + k \boldsymbol b \in V$，则对于 $\forall 0 \leq i \leq k$，都有 $\boldsymbol a + i \boldsymbol b \in V$。
设 $\boldsymbol a = \left( r, c \right), \boldsymbol b = \left( u, v \right)$。
不妨假设 $u > 0, v = 0$。其余部分留作练习。
由条件知 $\left( r n, c m \right)$ 和 $\left( \left( r + k u \right) n, c m \right)$ $4-$连通。
故存在一条斜率处处存在的折线，连接 $\left( r n, c m \right)$ 和 $\left( r n + k \cdot u n, c m \right)$，且不经过方格的顶点和障碍。
于是，上述折线可以看成定义在 $\left[ r n, r n + k \cdot u n \right]$ 上的函数 $f$，满足 $f \left( r n \right) = f \left( r n + k \cdot u n \right) = c m$。
由迷宫的周期性知，将上述折线向上 (负方向) 平移 $u n$ 个单位，所得到的折线仍满足不经过方格的顶点和障碍。记新的折线所对应的函数为 $g$，它满足 $g \left( x \right) = f \left( x + u n \right), g \left( r n - u n \right) = g \left( r n + \left( k - 1 \right) \cdot u n \right) = c m$。
定义 $h : \left[ r n, r n + \left( k - 1 \right) \cdot u n \right] \to \mathbb R, h \left( x \right) = f \left( x \right) - g \left( x \right)$。则 \begin{align*} \sum_{i=0}^{k-1} h \left( r + i \cdot u n \right) &= \sum_{i=0}^{k-1} \left( f \left( r + i \cdot u n \right) - g \left( r + i \cdot u n \right) \right) \\ &= \sum_{i=0}^{k-1} \left( f \left( r + i \cdot u n \right) - f \left( r + \left( i + 1 \right) \cdot u n \right) \right) \\ &= f \left( r \right) - f \left( r + k \cdot u n \right) \\ &= 0 \end{align*}
于是 $h \left( r \right), h \left( r + u n \right), \cdots, h \left( r + \left( k - 1 \right) u n \right)$ 不能全取正值或全取负值，因此这些值中必有零或既有正值又有负值。
若这些值中既有正值又有负值，由于 $h \left( x \right)$ 是连续函数，因此存在 $\xi$ 满足 $h \left( \xi \right) = 0$。
总之，总存在 $\xi \in \left[ r n, r n + \left( k - 1 \right) \cdot u n \right]$ 满足 $h \left( \xi \right) = 0$，即 $f \left( \xi \right) = g \left( \xi \right)$。
由几何意义知，这两条折线相交。从而 $\left( r n, c m \right)$ 和 $\left( r n + \left( k - 1 \right) \cdot u n, c m \right)$ $4-$连通。
重复上述过程知，对于每个 $0 \leq i \leq k$，均有 $\left( r + i \cdot u, c \right) \in V$。
在上述定理中取 $\boldsymbol a = \left( 0, 0 \right)$ 立即知道，对于每个 $V$ 中的向量 $\left( u, v \right)$，我们可以立即将 $u, v$ 中的最大公约数 $d = \left( u, v \right)$ 除掉，得到 $\left( \dfrac ud, \dfrac vd \right) \in V$。
因此，(推论) $V$ 只有三种可能形式：$V = \left\{ \left( 0, 0 \right) \right\}, V = \left\{ \left( k u, k v \right) \mid \gcd \left( u, v \right) = 1 \right\}, V = \mathbb Z^2$。
根据 $V$ 中向量的类型分类讨论。
$V = \left\{ \left( 0, 0 \right) \right\}$。
此即第一类情形。
$V$ 中存在非零向量，但所有向量都共线。
此即第二类情形。
$V$ 中存在两个不共线的非零向量。
任取 $\left( u, v \right) \in V \setminus \left\{ \left( 0, 0 \right) \right\}$ 且 $\gcd \left( u, v \right) = 1$ (为避免歧义使用 $\gcd$)，则直线 $- v x + u y = 0$ 上的所有整点都在 $V$ 中。
再取 $\left( r, s \right)$ 满足 $D = - v r + u s = \begin{vmatrix} u & v \\ r & s \end{vmatrix} \neq 0$。
由于 $\gcd \left( u, v \right) = 1$，因此由 Bézout 定理知存在 $A, B \in \mathbb Z$ 满足 $A u + B v = 1$。
设 $\boldsymbol w = \left( - B D, A D \right)$，则 $$ \left( \boldsymbol w - \left( r, s \right) \right) \times \left( u, v \right) = \left( - B D - r \right) v - \left( A D - s \right) u = \left( - B v - A u \right) D + \left( u s - v r \right) = \left( 1 - A u - B v \right) D = 0 $$
从而 $\boldsymbol w = \left( - B D, A D \right) \in V$，由介值性质知 $\left( - B, A \right) \in V$，而 $\begin{vmatrix} u & v \\ -B & A \end{vmatrix} = A u + B v = 1$，因此知 $\left| D \right|_\min = 1$。
(事实上，若一组 $\mathbb Z^2$ 格中基向量构成的行列式为 $1$，那么这个格基一定同构于 $\mathbb Z^2$)
因此 $- v x + u y = 0$ 和 $- v x + u y = 1$ 的所有整点都在 $V$ 中。由线性性质知 $- v x + u y = C$ ($C$ 是任意整数) 的所有整点都在 $V$ 中，即 $\mathbb Z^2 \subseteq V \Rightarrow V = \mathbb Z^2$。
现在考虑如何求解 $V$ 的形式。
我们考虑从原点开始宽度优先搜索 (bfs)，当然直接 bfs 是不行的，因为迷宫是无穷大的。因此我们限制余坐标相同的方格至多访问一遍。这样 bfs 的复杂度是 $O \left( n m \right)$ 的，且我们可以知道那哪些余坐标是可能访问到的，哪些余坐标是不可能访问到的 (ps: 这种情况确实是有可能的，比如中间有一个洞被障碍填了一圈)。
设所有可能被访问到的余坐标的集合为 $U$，对于一个余坐标 $\boldsymbol c = \left( r_T, c_T \right) \in U$，设所有余坐标为 $\boldsymbol c$ 的点中，和 $\left( 0, 0 \right)$ $4-$连通的点的块坐标集合为 $V_\boldsymbol c \neq \varnothing$。
下面根据 $V$ 的三种形式进行讨论：
$V = \left\{ \left( 0, 0 \right) \right\}$。
可以证明，对于每个余坐标 $\boldsymbol c = \left( r_T, c_T \right) \in U$，$\left| V_\boldsymbol c \right| = 1$。
反之，说明一个余坐标可以被两个块坐标 $\boldsymbol b_1, \boldsymbol b_2$ 访问。考虑其中一个块坐标回到 $\left( 0, 0 \right)$ 的路线，将该路线应用于另一个块坐标，可得余坐标为 $\left( 0, 0 \right)$ 的点也有至少两个块坐标 (与其连通)，与 $V = \left\{ \left( 0, 0 \right) \right\}$ 矛盾。
于是，在 bfs 结束后可以发现，每个余坐标所对应 (连通) 块坐标要么没有，要么唯一。
$V = \left\{ \left( k u, k v \right) \mid \gcd \left( u, v \right) = 1 \right\}$
不难证明，对于每个 $\boldsymbol c \in U$，$V_\boldsymbol c$ 中的向量总有无穷多个，且共线 (但这条线不一定经过原点)。
在 bfs 的过程中的表现就是，我们在扩展一个点时，会遇到一个点 $A$，它会扩展到一个 $B$，满足 $B$ 和一个已访问过的点有相同的余坐标但块坐标不相同。
此时，设 $\left( u', v' \right)$ 为那两个块坐标之差。$\left( u, v \right) = \dfrac 1d \left( u', v' \right)$ (其中 $\gcd \left( u', v' \right) = d$) (ps: 事实上可以证明，如果你使用的确实是 bfs 的话，那么此时一定有 $\gcd \left( u', v' \right) = 1$)。
从而，在 bfs 结束后可以发现，每个余坐标所对应的 (连通) 块坐标 (如果非空) 恰好是一条倾斜角固定的出现上的所有整点 (因此记录一个全局的倾斜角 (方向向量) 和每个 $V_\boldsymbol c$ 中的特定元素即可)。
$V = \mathbb Z^2$。
首先和 2 类似，我们可以得到一个向量 $\left( u, v \right)$，将其称为特征向量。
那么，如果 $V = \mathbb Z^2$，我们一定会在 bfs 的某一步，得到两个不平行的特征向量 (反证法，反设所有的特征向量都平行，那么容易证明一定是情形 2)。
也就是说出，一旦遇到这种情况，我们就可以断定 $V = \mathbb Z^2$，甚至对于每个 $\boldsymbol c \in U$，都有 $V_\boldsymbol c = \mathbb Z^2$。从而我们只需得到集合 $U$ 即可，而 $U$ 容易通过 bfs 得到。
因此，在 bfs 结束后可以发现，每个余坐标所对应的 (连通) 块坐标要么没有，要么就是 $\mathbb Z^2$。
现在考虑处理询问。设一组询问的块坐标是 $\left( r_B, c_B \right)$，余坐标是 $\boldsymbol c = \left( r_T, c_T \right)$，其实它的本质就是询问是否有 $\left( r_B, c_B \right) \in V_\boldsymbol c$。
根据上述三种情形讨论即可，由于每种情形集合 $V$ 都是一个看起来比较 "舒服" 的集合，因此可以在 $O \left( 1 \right)$ 时间内完成判断。
时间复杂度 $O \left( n m + q \right)$。
#include <bits/stdc++.h>
#define EB emplace_back
#define gcd std::__gcd
using std::cin;
using std::cout;
using std::vector;
typedef unsigned int u32;
typedef unsigned long long u64;
typedef std::pair <int, int> pr;
const int N = 108, er[4] = {0, -1, 0, 1}, ec[4] = {-1, 0, 1, 0};
bool FULL = false;
int R, C;
char s[N][N];
pr que[32767], eigen;
pr block[N][N], none;
std::unordered_set <u64> S;
inline pr dv(int a, int b) {
int q = a / b, r = a % b;
return pr(q + (r >> 31), r + (r >> 31 & b));
}
void bfs() {
int h, t = 1, r, c, d, nr, nc, Br, Bc, Tr, Tc, dr, dc, D;
S.reserve(32767), memset(&none, 127, sizeof none),
memset(block, 127, sizeof block), **block = pr(0, 0), S.emplace(0);
for (h = 0; h < t; ++h) {
std::tie(r, c) = que[h];
for (d = 0; d < 4; ++d) {
nr = r + er[d], std::tie(Br, Tr) = dv(nr, R),
nc = c + ec[d], std::tie(Bc, Tc) = dv(nc, C);
if (s[Tr][Tc] & 1) continue;
if (S.emplace((u32)nr | (u64)nc << 32).second) {
if (block[Tr][Tc] == none)
que[t++] = pr(nr, nc), block[Tr][Tc] = pr(Br, Bc);
else if (!FULL) {
dr = Br - block[Tr][Tc].first, dc = Bc - block[Tr][Tc].second;
if (eigen == pr(0, 0)) D = gcd(dr, dc), eigen = pr(dr / D, dc / D);
else if (dr * eigen.second != dc * eigen.first) FULL = true;
}
}
}
}
}
int main() {
int i, q, r, c, Br, Bc, Tr, Tc, dr, dc; bool ans;
std::ios::sync_with_stdio(false), cin.tie(NULL);
cin >> R >> C;
for (i = 0; i < R; ++i) cin >> s[i];
bfs();
for (cin >> q; q; --q) {
cin >> r >> c, std::tie(Br, Tr) = dv(r, R), std::tie(Bc, Tc) = dv(c, C);
if (FULL) ans = block[Tr][Tc] != none;
else if (eigen != pr(0, 0)) {
if (block[Tr][Tc] == none) ans = false;
else
dr = Br - block[Tr][Tc].first, dc = Bc - block[Tr][Tc].second,
ans = dr * eigen.second == dc * eigen.first;
} else ans = block[Tr][Tc] == pr(Br, Bc);
cout << (ans ? "yes\n" : "no\n");
}
return 0;
}
坑1：bfs 的时候队列要开到 $n m$ 级别，注意如果一个余坐标已经搜到过，则不能将其加入队尾，防止扩展到大量无效点 (从而向某些题解一样要搜 $10^6$ 步还卡常)。
坑2：可以用 $\left( + \infty, + \infty \right)$ 来表示某个 $V_\boldsymbol c$ 为空，但不能用 $\left( 0, 0 \right)$ 表示。