26 pts 求助
查看原帖
26 pts 求助
278605
梨衣楼主2020/11/21 11:51

剩下点都 WAWA 了,一小时没调出来,求助

#include<cstdio>
#include<iostream>
#include<queue>
using namespace std;
int n,m,sx,sy,tx,ty;
char c[310][310];
int step[310][310],v[310][310];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
queue<int>qx,qy;
void bfs(){
	while(!qx.empty()){
		int cx=qx.front(),cy=qy.front();
		//if(cx==tx&&cy==ty)return;
		qx.pop(),qy.pop();
		for(int ii=0;ii<4;ii++){
			int xx=cx+dx[ii],yy=cy+dy[ii];
			if(xx>0&&xx<=n&&yy>0&&yy<=m&&c[xx][yy]!='#'){
				if(c[xx][yy]>='A'&&c[xx][yy]<='Z'){
					for(int i=1;i<=n;i++)
						for(int j=1;j<=m;j++)
							if(c[i][j]==c[xx][yy]&&i!=xx&&j!=yy&&!v[i][j]){
								v[i][j]=1;
								step[i][j]=step[cx][cy]+1;
								if(i==tx&&j==ty)return;
								qx.push(i),qy.push(j);
								break;
							} 
				}		
				else {
					if(v[xx][yy])continue;
					step[xx][yy]=step[cx][cy]+1;
					if(xx==tx&&yy==ty)return;
					v[xx][yy]=1;
					qx.push(xx),qy.push(yy);
				}
			}
		}
	}
}
int main(){
//	freopen("1.txt","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			cin>>c[i][j];
			if(c[i][j]=='@')sx=i,sy=j;
			if(c[i][j]=='=')tx=i,ty=j;
		}
	v[sx][sy]=1;
	qx.push(sx),qy.push(sy);
	bfs();
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=m;j++)
//		printf("%5c",c[i][j]);
//		printf("\n");
//	}
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=m;j++)
//			printf("%5d",step[i][j]);
//		printf("\n");
//	}
	printf("%d",step[tx][ty]);
} 
2020/11/21 11:51
加载中...