CF1063B 求助
查看原帖
CF1063B 求助
247220
StarryWander楼主2021/2/28 16:45

这道题虽然有个坑,虽然有意识地避开,但是在那些测试点还是过不去,就是在遇到“+”时(已经走过的地方)有更优的路线就重新push进队列,我这样的做法有什么问题吗?

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct node{
	int x,y,l,r;
};
int n,m,sx,sy,l,r,ans=1;
node off[4]={{0,1,0,1},{1,0,0,0},{0,-1,1,0},{-1,0,0,0}};
char a[2005][2005];
node p[2005][2005];
int main(){
	cin>>n>>m>>sx>>sy>>l>>r;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	queue<node>q;
	q.push((node){sx,sy,0,0});
	a[sx][sy]='+'; 
	p[1][1].l=p[1][1].r=0;
	while(!q.empty()){
		node k=q.front();
		for(int i=0;i<4;i++){
			int x=k.x+off[i].x;
			int y=k.y+off[i].y;
			int nl=k.l+off[i].l;
			int nr=k.r+off[i].r;
			if(x>=1&&x<=n&&y>=1&&y<=m){
				if(a[x][y]=='.'&&nl<=l&&nr<=r){
					q.push((node){x,y,nl,nr});
					p[x][y].l=nl;
					p[x][y].r=nr;
					a[x][y]='+';
					ans++;
				}
				else if(a[x][y]=='+'){
					if(nl<p[x][y].l&&nr<p[x][y].r){
						q.push((node){x,y,nl,nr});
						p[x][y].l=nl;
						p[x][y].r=nr;
					}
					else a[x][y]='*';
				}
			}
		}
		q.pop();
	}
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=m;j++){
//			cout<<a[i][j];
//		}
//		cout<<endl;
//	}
	cout<<ans;
	return 0;
}

2021/2/28 16:45
加载中...