牛客2021暑期训练8-F-Robots

牛客2021暑期训练8-F-Robots

题目链接

题意

一个 $n\ast m$ 的地图，$0$ 可达 $1$ 不可达，有三种机器人，只能向下走、只能向右走、可以向下向右走，对给的 $q$ 个机器人能否从 $(x1,y1)$走到 $(x2,y2)$

题解

主要记录下 $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;
}