WA+MLE求助!!!用的广搜
查看原帖
WA+MLE求助!!!用的广搜
1255488
__notTrueLight__楼主2024/6/28 14:08
#include<iostream>
#include<queue>
using namespace std;
int vmap[16384][8005];//记录是否已被经过
//行,列,当前坐标,哈利坐标,飞贼坐标,判断是否看到// 
int a,b,x,y,sx,sy,ex,ey,pd;
char map[16384][8005];//记录地图 
queue<int>qy;queue<int>qx;//未搜索队列 
int main(){
	cin>>a>>b;//初始化地图 
	for(int i=0;i<a;i++){
		for(int ii=0;ii<b;ii++){
			cin>>map[i][ii];
			vmap[i][ii]=0;
			if(map[i][ii]=='X'){vmap[i][ii]=-1;}
		}
	}
while(1){//开始输入坐标 
	cin>>ey>>ex>>sy>>sx;
	if(!sy || !sx || !ey || !ex){break;}
	sx--;sy--;ex--;ey--;
	while(!qx.empty())qx.pop();//初始化队列 
	while(!qy.empty())qy.pop();
	for(int i=0;i<a;i++){
		for(int ii=0;ii<b;ii++){//初始化"被经过地图" 
			vmap[i][ii]=0;
			if(map[i][ii]=='X'){vmap[i][ii]=-1;}
		}
	}
	qx.push(sx);qy.push(sy);//从起点开始 
	pd=0;
	while(!qx.empty() || !qy.empty()){//直到无路可走 
		x=qx.front();y=qy.front();//当前位置 
		if(x==ex && y==ey){pd=1;break;}//判断是否到达终点 
		if(x && y){//往左上看 
			if(y-1==ey && x-1==ex){pd=1;break;}
		}
		if(x<b-1 && y<a-1){//往右下看 
			if(y+1==ey && x+1==ex){pd=1;break;}
		}
		if(x<b-1 && y){//往右上看 
			if(y-1==ey && x+1==ex){pd=1;break;}
		} 
		if(y<a-1 && x){//往左下看 
			if(y+1==ey && x-1==ex){pd=1;break;}
		}
		if(y){//往上看
			if(y-1==ey && x==ex){pd=1;break;
			}else if(map[y-1][x]=='O' && !vmap[y-1][x]){ 
				qy.push(y-1);//往上走
				qx.push(x);
				vmap[y-1][x]=vmap[y][x]+1;
			}
		}
		if(y<a-1){//往下看
			if(y+1==ey && x==ex){pd=1;break;
			}else if(map[y+1][x]=='O' && !vmap[y+1][x]){
				qy.push(y+1);//往下走 
				qx.push(x);
				vmap[y+1][x]=vmap[y][x]+1;
			}
		}
		if(x){//往左看 
			if(y==ey && x-1==ex){pd=1;break;
			}else if(map[y][x-1]=='O' && !vmap[y][x-1]){
				qy.push(y);//往左走 
				qx.push(x-1);
				vmap[y][x-1]=vmap[y][x]+1;
			}
		}
		if(x<b-1){//往右看 
			if(y==ey && x+1==ex){pd=1;break;
			}else if(map[y][x+1]=='O' && !vmap[y][x+1]){
				qy.push(y);//往右走 
				qx.push(x+1);
				vmap[y][x+1]=vmap[y][x]+1;
			}
		}
		qx.pop();qy.pop();//弹出 
	}
	if(pd){//判断是否看到飞贼 
		cout<<vmap[y][x]<<endl;
	}else{//若没有看到飞贼
		cout<<"Poor Harry"<<endl;
	}
}
	return/*191981*/0;
}

蒟蒻求助!!!

2024/6/28 14:08
加载中...