题解 | #Robots#

F题题解
(本人也是菜鸡,如有错误请大佬指正QWQ)
题目大意:
在nXm的图上有些障碍物，有三种机器人
1:只会往下走
2:只会往右走
3:又会右走又会下走
现给出Q个机器人，已知其起点，终点，类型，问机器人能否到达终点
机器人数量很多(5e5)，而地图很小(500*500)
这就可以考虑离线做法，维护终点，判断哪些起点可以到达该终点
用一个结构体来储存这些机器人问询
t代表机器人类型，id代表机器人编号,x,y为起点编号

struct node {
int t, x, y, id;
};
vector<node>q[i][j];储存终点为i,j的问询
接下来就是如何维护的问题
如果开四维数组铁定爆空间
所以可以用类似滚动数组的方式:开出一个三维数组，a[k][i][j] K代表当前遍历到的点的横坐标,i,j组成可达性矩阵
当遍历一个点(i,j)时，如果这个点上没有障碍物，说明这个点可以到达它自己，所以a[j][i][j]=1.同时，那么就说明能够到达其左边的点的起点也可以到达当前点，其左边的点能到达的地方这个点也能到达，所以将a[j-1][i][j]的可达性矩阵拷贝给a[j][i][j]
如果这个点上有障碍物，那么代表从任何点出发，都无法到达当前点
由于用数组进行以上操作过于麻烦，可以尝试用bitset来实现
bitset<N N>b[N];
这个可以将其理解为开了N个长度为NN的一维数组
b[k][i*m+j]就可以等同于a[k][i][j]；
拷贝操作:b[j] |= b[j - 1];
这个操作非常重要，注意到运算符是 | ，代表着b[j]和b[j-1]中的某一位只要其中一位是1，那么b[j]就是1
在看前面的讲解有说到:只要到达其左边的点，就能到达该点
那么为什么不提上面的点?能到达其上方的点，同样能到达该点
这就是滚动数组的延迟更新的特性,这能到达其上方的点，本身就已经在上一轮循环中储存在b[j]里了
举个例子，这是一张地图:
0 0 0
0 0 0
0 1 0
图中1代表障碍物,0代表空地
在遍历(1,1)时，b[1]的可达性矩阵是这样的
1 0 0
0 0 0
0 0 0
在遍历(1,2)时，由于b[2]|=b[1],其的可达性矩阵是这样的
1 1 0
0 0 0
0 0 0
在遍历(1,3)时，b[3]的可达性矩阵是这样的
1 1 1
0 0 0
0 0 0
在遍历(2,1)时,在未更新b[1]前，b[1]可达性矩阵是这样
1 0 0
0 0 0
0 0 0
在更新b[1]后，b[1]可达性矩阵是这样
1 0 0
1 0 0
0 0 0
在遍历(2,2)时，未更新b[2]前，b[2]可达性矩阵是这样
1 1 0
0 0 0
0 0 0
在进行b[2]|=b[1]操作后，b[2]成了这样
1 1 0
1 1 0
0 0 0
现在快进一波,在遍历(3,2)时，由于(3,2)有障碍物，其可达性矩阵要全部清0
此时的b[2]变成了
0 0 0
0 0 0
0 0 0
接下来遍历(3,3)，在更新数据前b[3]是这个样子
1 1 1
1 1 1
0 0 0
在进行b[3]|=b[2]更新后，再加上它本身，变成这个样子:
1 1 1
1 1 1
0 0 1
由此，就实现了高效维护
代码</node>

#include <bits/stdc++.h>
using namespace std;
const int N = 505;

struct node {
    int t, x, y, id;
};

vector<node>q[N][N];
bitset<N *N>b[N];
int ans[500005];
char s[N][N];

int main() {
    int n, m, Q, x1, x2, y1, y2, t;
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> s[i][j];
        }
    }
    cin >> Q;
    for (int i = 1; i <= Q; i++) {
        cin >> t >> x1 >> y1 >> x2 >> y2;
        q[x2][y2].push_back({t, x1, y1, i});//注意:是反着的，终点为x2,y2
        //将x1,y1到x2,y2 变成 x2,y2到x1,y1
    }
    b[0].reset();
    //类滚动数组
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {

            if (s[i][j] == '0') {
                b[j] |= b[j - 1];//拷贝上一份
                b[j][i * m + j] = 1;//自己到自己是1
            } else {
                b[j].reset();//全部是0,当前点是无论如何都不能到达任何地方的
            }
            for (auto it : q[i][j]) {
                if (it.t == 1) {
                    ans[it.id] = (it.y == j && b[j][it.x * m + it.y]);
                } else if (it.t == 2) {
                    ans[it.id] = (it.x == i && b[j][it.x * m + it.y]);
                } else {
                    ans[it.id] = b[j][it.x * m + it.y];
                }
            }
        }
    }
    for (int i = 1; i <= Q; i++) {
        if (ans[i]) {
            cout << "yes" << endl;
        } else {
            cout << "no" << endl;
        }
    }
}