牛客2021暑期训练8-F-Robots
题目链接
题意
一个
n
?
m
n*m
n?m 的地图，
0
0
0 可达
1
1
1 不可达，有三种机器人，只能向下走、只能向右走、可以向下向右走，对给的
q
q
q 个机器人能否从
(
x
1
,
y
1
)
(x1,y1)
(x1,y1)走到
(
x
2
,
y
2
)
(x2,y2)
(x2,y2)
题解
主要记录下
b
i
t
s
e
t
bitset
bitset 存可达图
代码
#include<bits/stdc++.h>
#define Pb push_back
using namespace std;
const int N=509,M=5e5+9;
int n,m,q;
int ans[M];
char s[N][N];
struct node
{
int t,x,y,p;
};
vector<node>v[N][N];
bitset<N*N>mp[N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
scanf("%s",s[i]+1);
cin>>q;
for(int i=1;i<=q;i++)
{
int t,x1,y1,x2,y2;
cin>>t>>x1>>y1>>x2>>y2;
v[x2][y2].Pb(node{t,x1,y1,i});
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(s[i][j]=='1') mp[j].reset();
else
{
mp[j]|=mp[j-1];
mp[j][(i-1)*m+j]=1;
}
for(auto k:v[i][j])
{
if(k.t==1) ans[k.p]=(k.y==j&&mp[j][(k.x-1)*m+k.y]);
else if(k.t==2) ans[k.p]=(k.x==i&&mp[j][(k.x-1)*m+k.y]);
else ans[k.p]=mp[j][(k.x-1)*m+k.y];
}
}
for(int i=1;i<=q;i++)
cout<<(ans[i]?"yes":"no")<<endl;
return 0;
}
|