cf232E. Quick Tortoise(分治 bitset dp)
程序员文章站
2022-05-07 07:53:23
题意 "题目链接" Sol 感觉这个思路还是不错的 cpp include using namespace std; const int MAXN = 501, SS = 5e6 + 10; inline int read() { char c = getchar(); int x = 0, f = ......
题意
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 */