下面认为 \(m=n\)。
有一个显然的暴力：对每个点 \((x,y)\)，预处理出另外所有点 \((p,q)\) 是否能到达 \((x,y)\)，记为 \(f_{p,q,x,y}\)。查询 \(O(1)\)，但是预处理 \(O(n^4)\)。用 bitset 优化即可做到 \(O(q+\frac{n^4}{\omega})\)，可惜仍然过不了。
考虑把一个 \(n\) 变成 \(\log n\)，可以考虑类似猫树分治的东西。对 \(x\) 轴进行分治，假设分治区间为 \([l,r]\)，处理 \(x_0\le \text{mid},x_1\ge \text{mid}\) 的询问。记录\(f_{x,y,k}\) 为 \(x\le l\) 的 \((x,y)\) 是否能走到 \((\text{mid}, k)\)，\(g_{x,y,k}\) 为 \(x\ge l\) 的 \((x,y)\) 是否能从 \((\text{mid},k)\) 走到。复杂度是 \(O(n^3\log n+q\log n)\) 的。
此时再使用 bitset 优化即可做到 \(O\left(\frac{n^3\log n}{\omega}+q\left(\log n+\frac{n}{\omega}\right)\right)\)。
还是很暴力。
#include <bits/stdc++.h>
using namespace std;
namespace vbzIO {
char ibuf[(1 << 20) + 1], *iS, *iT;
// #if ONLINE_JUDGE
// #define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
// #else
#define gh() getchar()
// #endif
#define pc putchar
#define pi pair<int, int>
#define tu3 tuple<int, int, int>
#define tu4 tuple<int, int, int, int>
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define ins insert
#define era erase
inline int read () {
char ch = gh();
int x = 0;
bool t = 0;
while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
return t ? ~(x - 1) : x;
}
inline void write(int x) {
if (x < 0) {
x = ~(x - 1);
putchar('-');
}
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
}
using vbzIO::read;
using vbzIO::write;
const int maxn = 550;
const int maxm = 6e5 + 600;
struct node { int lx, rx, ly, ry, id; } q[maxm], ql[maxm], qr[maxm];
int n, m, k, ans[maxm];
char c[maxn][maxn];
bitset<maxn> f[maxn][maxn], g[maxn][maxn];
void conq(int l, int r, int s, int t) {
if (l == r || s > t) {
for (int i = 1; i <= m; i++)
f[l][i].reset();
for (int i = 1; i <= m; i++) if (c[l][i] == '.') f[l][i][i] = 1;
for (int i = m - 1; i; i--) if (c[l][i] != '#') f[l][i] |= f[l][i + 1];
for (int i = s; i <= t; i++) ans[q[i].id] = (f[l][q[i].ly] & f[l][q[i].ry]).any();
return;
}
int mid = (l + r) >> 1;
for (int i = l; i <= r; i++)
for (int j = 1; j <= m; j++)
f[i][j].reset(), g[i][j].reset();
for (int i = 1; i <= m; i++)
if (c[mid][i] == '.') f[mid][i][i] = g[mid][i][i] = 1;
for (int i = m - 1; i; i--)
if (c[mid][i] != '#') f[mid][i] |= f[mid][i + 1];
for (int i = 2; i <= m; i++)
if (c[mid][i] != '#') g[mid][i] |= g[mid][i - 1];
for (int i = mid - 1; i >= l; i--) {
for (int j = m; j; j--) {
if (c[i][j] == '#') continue;
f[i][j] |= f[i + 1][j];
if (j < m) f[i][j] |= f[i][j + 1];
}
}
for (int i = mid + 1; i <= r; i++) {
for (int j = 1; j <= m; j++) {
if (c[i][j] == '#') continue;
g[i][j] |= g[i - 1][j];
if (j > 1) g[i][j] |= g[i][j - 1];
}
}
int cl = 0, cr = 0;
for (int i = s; i <= t; i++) {
if (q[i].lx > mid && q[i].rx > mid) qr[++cr] = q[i];
else if (q[i].lx <= mid && q[i].rx <= mid) ql[++cl] = q[i];
else ans[q[i].id] = (f[q[i].lx][q[i].ly] & g[q[i].rx][q[i].ry]).any();
}
for (int i = s; i <= s + cl - 1; i++) q[i] = ql[i - s + 1];
for (int i = s + cl; i <= s + cl + cr - 1; i++) q[i] = qr[i - s - cl + 1];
conq(l, mid, s, s + cl - 1), conq(mid + 1, r, s + cl, s + cl + cr - 1);
}
int main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
n = read(), m = read();
for (int i = 1; i <= n; i++) scanf("%s", c[i] + 1);
k = read();
for (int i = 1, a, b, c, d; i <= k; i++) {
a = read(), b = read(), c = read(), d = read();
q[i] = (node) { a, c, b, d, i };
}
conq(1, n, 1, k);
for (int i = 1; i <= k; i++)
puts(ans[i] ? "Yes" : "No");
return 0;
}