社区讨论

求调,不知道哪错了

P2199最后的迷宫参与者 3已保存回复 6

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@lo24x5ks
此快照首次捕获于
2023/10/23 08:03
2 年前
此快照最后确认于
2023/11/03 08:21
2 年前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,sx,sy,ex,ey;
string s[N],vis[N],vis2[N];
const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};
const int nx[]={1,-1,0,0,1,-1,-1,1};
const int ny[]={0,0,1,-1,1,-1,1,-1};
struct node{
	int x,y,step;
	bool operator<(const node &a)const{
		return step>a.step;
	}
};priority_queue<node>q,qq;
bool check(int x,int y){
	if(x<1||x>n||y<1||y>m||s[x][y]=='X'||vis[x][y]=='1')return 0;
	else return 1;
}
bool check2(int x,int y){
	if(x<1||x>n||y<1||y>m||s[x][y]=='X'||vis2[x][y]=='1')return 0;
	else return 1;
}
bool look(int stx,int sty){
	while(qq.size())qq.pop();
	qq.push({stx,sty});
	for(int i=1;i<=n;++i)vis2[i]="";
	vis2[stx][sty]='1';
	while(qq.size()){
		node k=qq.top();
		qq.pop();
		if(k.x==ex&&k.y==ey)return 1;
		for(int i=0;i<8;++i){
			int xx=nx[i]+k.x;
			int yy=ny[i]+k.y;
			if(!check2(xx,yy))continue;
			qq.push({xx,yy});
			vis2[xx][yy]='1';
		}
	}
	return 0;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;++i){
		cin>>s[i];
		s[i]=' '+s[i];
	}
	while(1){
		scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
		bool flag=1;
		if(sx==sy&&sy==ex&&ex==ey&&ey==0)return 0;
		while(q.size())q.pop();
		q.push({sx,sy,0});
		for(int i=1;i<=n;++i)vis[i]="";
		vis[sx][sy]='1';
		while(q.size()){
			node now=q.top();
			//cout<<now.x<<" "<<now.y<<"\n";
			q.pop();
			if(look(now.x,now.y)){
				printf("%d\n",now.step);
				flag=0;
				break;
			}
			for(int i=0;i<4;++i){
				int xx=dx[i]+now.x;
				int yy=dy[i]+now.y;
				if(!check(xx,yy))continue;
				q.push({xx,yy,now.step+1});
				vis[xx][yy]=1;
			}
		}
		if(flag)printf("Poor Harry\n");
	}
	return 0;
}
话说这题应该挺水的啊。。。

回复

6 条回复,欢迎继续交流。

正在加载回复...