38WA求助
查看原帖
38WA求助
916086
yaoshuen楼主2023/7/5 14:11
#include <bits/stdc++.h>
using namespace std;
int n,m;
struct Point{
	int x;
	int y;
};
struct dor{
	int x;
	int y;
	char ch;
};
vector<dor>tp;
Point d[321][321];
int a[320][320];
Point start,goal;
char ch;
struct bfs{
	int x;
	int y;
	int t;
};
queue<bfs>q;
bool h[320][320];
int x,y,t,tx,ty;
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
int main(){
	scanf("%d%d",&n,&m);
	getchar();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			scanf("%c",&ch);
			if(ch=='#') a[i][j]=1;
			else if(ch=='.') a[i][j]=0;
			
			else if(ch>='A'&&ch<='Z'){
				bool f=0;
				for(int k=0;k<tp.size();k++){
					if(tp[k].ch==ch){
						f=1;
						d[i][j].x=tp[k].x;
						d[i][j].y=tp[k].y;
						d[tp[k].x][tp[k].y].x=i;
						d[tp[k].x][tp[k].y].y=j;
						break;
					}
				}
				if(!f){
					tp.push_back(dor{i,j,ch});
				}
			}
			
			else if(ch=='=') goal.x=i,goal.y=j;
			else if(ch=='@') start.x=i,start.y=j;
		}
		getchar();
	}
	//printf("%d %d %d %d",start.x,start.y,goal.x,goal.y);
	/*for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			printf("%d ",a[i][j]);
		}
		printf("\n");
	}*/
	/*for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			printf(" %d,%d->%d,%d ",i,j,d[i][j].x,d[i][j].y);
		}
		printf("\n");
	}*/
	
	//bfs
	h[start.x][start.y]=1;
	q.push(bfs{start.x,start.y,0});
	while(!q.empty()){
		x=q.front().x;
		y=q.front().y;
		t=q.front().t;
		q.pop();
		if(x==goal.x&&y==goal.y){
			printf("%d",t);
			exit(0);
		}
		
		if(d[x][y].x!=0&&d[x][y].y!=0&&!h[d[x][y].x][d[x][y].y]){
			q.push(bfs{d[x][y].x,d[x][y].y,t});
			h[d[x][y].x][d[x][y].y]=1;
		}
		for(int i=0;i<4;i++){
			tx=x+dx[i];
			ty=y+dy[i];
			if(tx>0&&tx<=n&&ty>0&&ty<=m&&a[tx][ty]==0&&!h[tx][ty]){
				//else{
					h[tx][ty]=1;
					q.push(bfs{tx,ty,t+1});
				//}
			}
		}
	}
	return 0;
}

2023/7/5 14:11
加载中...