38分求助
查看原帖
38分求助
176752
Hermkes楼主2021/8/20 21:56
#include<iostream> 
#include<cstring>
#include<cstdio> 
#include<cmath> 
#include<algorithm> 
#include<bits/stdc++.h>
using namespace std;
long long tot=0,i,d[500010],v[500010],s,h[500010],n,m,f;
char a[310][310];
long long dx[10]={0,1,-1,0,0};
long long dy[10]={0,0,0,1,-1};
queue<int> q;
struct tu{
	long long next,ver,edge;
}e[500010];
void add(long long x,long long y,long long z){
	tot++;
	e[tot].ver=y;
	e[tot].edge=z;
	e[tot].next=h[x];
	h[x]=tot;
}
void spfa(){
	for(i=1;i<=n;i++){
		d[i]=2147483647;
		v[i]=0;
	}
	d[s]=0;
	v[s]=1;
	q.push(s);
	long long xx,yy,zz;
	while(q.size()){
		xx=q.front();
		q.pop();
		v[xx]=0;
		for(i=h[xx];i;i=e[i].next){//cout<<e[i].ver<<endl;
			yy=e[i].ver;
			zz=e[i].edge;
			if(d[yy]>d[xx]+zz){
				d[yy]=d[xx]+zz;
				if(v[yy]==0){
					q.push(yy);
					v[yy]=1;
				}
			}
		}
	}
}
int main(){    
	cin>>n>>m;
	for(long long i=1;i<=n;i++){
		for(long long j=1;j<=m;j++){
			cin>>a[i][j];
			if(a[i][j]=='@'){s=(i-1)*m+j;}
			if(a[i][j]=='='){f=(i-1)*m+j;}
		}
	}
	for(long long i=1;i<=n;i++){
		for(long long j=1;j<=m;j++){
			if(a[i][j]!='#'){
				for(long long k=1;k<=4;k++){
					if(a[i+dx[k]][j+dy[k]]!='#'&&a[i+dx[k]][j+dy[k]]!=0){
						add((i-1)*m+j,(i-1+dx[k])*m+j+dy[k],1);
					}
				}
			}
			if(a[i][j]>='A'&&a[i][j]<='Z'){
				for(long long l=1;l<=n;l++){
					for(long long r=1;r<=m;r++){
						if(a[i][j]==a[l][r]){
							if(i==l&&j==r){continue;}//cout<<l<<" "<<r<<endl;
							add((i-1)*m+j,(l-1)*m+r,0);
						}	
					}
				}
			}
			
		}
	}
	n*=m;
	spfa();
	cout<<d[f];
	return 0;
}
2021/8/20 21:56
加载中...