2021牛客暑期多校训练营#8:F-Robots

2021牛客暑期多校训练营#8:F-Robots

原题链接：https://ac.nowcoder.com/acm/contest/11259/F

题目大意

有一个$n\times m(1\le n,m\le 500)$大小的网格，左上角是$(1,1)$右下角是$(n,m)$，其中有一些无法通过的格子。
有以下三种机器人：

1. 只能向下移动的机器人，即只能从$(x,y)$移动到 $(x+1,y)$；
2. 只能向右移动的机器人，即只能从$(x,y)$移动到$(x,y+1)$;
3. 既可以向下也可以向右移动的机器人；

有去$(1\le q\le 5?10^5）$次询问，每次询问$t$型机器人需要从起点$(x_1,y_1)$前往终点$(x_2,y_2)$,判断是否可行。

解题思路

$1、2$型机器人很好解决，可以使用前缀和快速判断起点与终点之间是否有障碍物。

$3$型机器人的判断，就十分难办，经过激烈的脑力风暴，我得出：不能在线判断！时间受不了！废话，于是经过进一步的思考，我想出了枚举起点到任意终点的方案或枚举终点从任意起点来的方案，由于每一点只能从上方或左边来，所以很显然成了个dp问题。
当我枚举每个点，每一个点都要向左边遍历每个点，判断是否有障碍物，但这是不现实的，肯定会T。
但是，如果第一个点能毫无阻拦地向左遍历一万个点，那第二个点肯定也是可以遍历的，所以第二个点的状态可以从第一个点转移。

代码实现

#include<bits/stdc++.h>
#define eb push_back
#define For(i,n,m) for(int i=n;i<=m;i++)
using namespace std;
const int M=510;
int n,m,q,x[M][M],y[M][M];
char c[M][M];
bool ans[M*1000];
bitset<M>vis[M];
struct nn{
    int rx,ly,ry,i;
};
vector<nn>ve[M],t[M];
void rd(int &x)
{
    int res=0;char c=getchar(),last=' ';while(c>'9'||c<'0')last=c,c=getchar();while(c<='9'&&c>='0')res=res*10+c-'0',c=getchar();x=last=='-'?-res:res;
}
int main()
{
    rd(n),rd(m);for(int i=1;i<=n;++i){
    scanf("%s",c[i]+1);for(int j=1;j<=m;++j)x[i][j]=x[i][j-1]+(c[i][j]=='1'),y[i][j]=y[i-1][j]+(c[i][j]=='1');}rd(q);for(int i=1;i<=q;++i){
    int o,lx,ly,rx,ry;scanf("%d%d%d%d%d",&o,&lx,&ly,&rx,&ry);if(o==1){
    if(ly==ry&&rx>=lx&&y[rx][ly]-y[lx-1][ly]==0)ans[i]=1;}else if(o==2){
    if(lx==rx&&ry>=ly&&x[lx][ry]-x[lx][ly-1]==0)ans[i]=1;}else if(lx<=rx&&ly<=ry)ve[lx].eb(nn{
    rx,ly,ry,i});}for(int l=1;l<=n;++l){
    for(auto o:ve[l])t[o.rx].eb(o);for(int i=1;i<=m;++i)vis[i].reset();for(int i=1;i<=m;++i)if(c[l][i]=='1')vis[i].reset();//如果有障碍，状态清零else vis[i][i]=1,vis[i]|=vis[i-1];//反之，转移，因为从i到i肯定有路可走，则为1，否则或上vis_{i-1},转移状态for(int r=l;r<=n;++r){
    for(int i=1;i<=m;++i){
    vis[i]|=vis[i-1];if(c[r][i]=='1')vis[i].reset();}for(auto o:t[r])ans[o.i]=vis[o.ry][o.ly];t[r].clear();}}for(int i=1;i<=q;i++)puts(ans[i]?"yes":"no");
}

PS

代码实现稍显复杂实在表现不出思路，见谅