题意

题目链接

Sol

感觉这个思路还是不错的

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 501, SS = 5e6 + 10;

inline int read() {

	char c = getchar(); int x = 0, f = 1;

	while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}

	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

	return x * f;

}

int N, M, Q, ans[SS];

char s[MAXN][MAXN];

bitset<MAXN> f[MAXN][MAXN], g[MAXN][MAXN], Empty;

struct Query {

	int x1, y1, x2, y2, id;

}q[SS];

void solve(int l, int r, vector<Query> q) {

	if(l > r) return ;

	vector<Query> lq, rq;

	int mid = l + r >> 1;

	//f[i][j]从i,j能到达的mid中的点集

	//g[i][j]从mid能到达i, j的点集

	for(int i = mid; i >= l; i--) {

		for(int j = M; j >= 1; j--) {

			f[i][j] = Empty;

			if(i == mid) f[i][j][j] = (s[i][j] == '.');

			if(i + 1 <= mid && s[i + 1][j] == '.') f[i][j] = f[i][j] | f[i + 1][j];

			if(j + 1 <= M && s[i][j + 1] == '.') f[i][j] = f[i][j] | f[i][j + 1];

		}

	}

	for(int i = mid; i <= r; i++) {

		for(int j = 1; j <= M; j++) {

			g[i][j] = Empty;

			if(i == mid) g[i][j][j] = (s[i][j] == '.');

			if(i - 1 >= mid && s[i - 1][j] == '.') g[i][j] = g[i][j] | g[i - 1][j];

			if(j - 1 >= 1 && s[i][j - 1] == '.') g[i][j] = g[i][j] | g[i][j - 1];

		}

	}

	for(auto &cur : q) {

		if(cur.x2 < mid) lq.push_back(cur);

		else if(cur.x1 > mid) rq.push_back(cur);

		else {

			//cout << f[cur.x1][cur.y1] << endl;

			//cout << g[cur.x2][cur.y2] << endl;

			ans[cur.id] = (f[cur.x1][cur.y1] & g[cur.x2][cur.y2]).count();

		}

	}

	solve(l, mid - 1, lq);

	solve(mid + 1, r, rq);

}

int main() {

	N = read(); M = read();

	for(int i = 1; i <= N; i++) scanf("%s", s[i] + 1);

	Q = read();

	vector<Query> now;

	for(int i = 1; i <= Q; i++) {

		q[i].x1 = read(), q[i].y1 = read(), q[i].x2 = read(), q[i].y2 = read(); q[i].id = i;

		now.push_back(q[i]);

	}

	solve(1, N, now);

	for(int i = 1; i <= Q; i++) puts(ans[i] ? "Yes" : "No");

	return 0;

}

/*

3 3

...

.##

.#.

1

1 1 3 1

3 3

...

.##

.#.

5

1 1 3 3

1 1 1 3

1 1 3 1

1 1 1 2

1 1 2 1

*/