前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >cf232E. Quick Tortoise(分治 bitset dp)

cf232E. Quick Tortoise(分治 bitset dp)

作者头像
attack
发布2019-01-30 16:52:05
4850
发布2019-01-30 16:52:05
举报
文章被收录于专栏:数据结构与算法

题意

题目链接

Sol

感觉这个思路还是不错的

代码语言:javascript
复制
#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
*/
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019-01-15 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题意
  • Sol
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档