UVA 2612 Find a way（BFS）

待我称王封你为后i 2024-02-17 19:07 31阅读 0赞

分别计算每个人到每个KCF的最短距离，然后相加求出最短距离

#include<cstdio>
    #include<queue>
    #include<cstring>
    using namespace std;
    const int maxn=200+10;
    struct node{
    	int x,y;
    	node(int x=0,int y=0):x(x),y(y){}
    }ny,nm;
    char g[maxn][maxn];       //输入路径 
    int d[maxn][maxn];
    int dy[maxn][maxn],dm[maxn][maxn];   //Y、M 
    int n,m;
    int total;           //计算出现过几次 @（KCF） 
    int dir[][2]={
       {1,0},{-1,0},{0,-1},{0,1}};
    bool isValid(node & nd){
    	return nd.x>=0&&nd.x<m && nd.y>=0&&nd.y<n;
    }
    void bfs(node &nd){
    	memset(d,0,sizeof(d));
    	queue<node>q;
    	q.push(nd);
    	while(!q.empty()){
    		node u=q.front();
    		q.pop();
    		if(g[u.y][u.x]=='@'){
    			if(total){if(g[nd.y][nd.x]=='Y')dy[u.y][u.x]=d[u.y][u.x];
    			else dm[u.y][u.x]=d[u.y][u.x];
    			}
    			if(--total==0)return ;
    		}
    		for(int i=0;i<4;i++){
    			node v=node(u.x+dir[i][0],u.y+dir[i][1]);
    			if(isValid(v) && !d[v.y][v.x] && g[v.y][v.x]!='#'){
    				q.push(v);
    				d[v.y][v.x]=d[u.y][u.x]+11;
    			}
    		}
    	}
    }
    int main(){
    	while(scanf("%d%d",&n,&m)==2){
    		getchar();
    		total=0;
    		for(int i=0;i<n;i++){
    			for(int j=0;j<m;j++){
    				scanf("%c",&g[i][j]);
    				if(g[i][j]=='Y')ny.y=i,ny.x=j;
    				if(g[i][j]=='M')nm.y=i,nm.x=j;
    				if(g[i][j]=='@')total++;
    			}
    			getchar();
    		}
    		int temp=total; 
    		memset(dy,0,sizeof(dy));
    		memset(dm,0,sizeof(dm)); 
    		bfs(ny);
    		total=temp;
    		bfs(nm);
    		int min1=1000000;
    		for(int i=0;i<n;i++){
    			for(int j=0;j<m;j++){
    				if(g[i][j]=='@' && dy[i][j]!=0&&dm[i][j]!=0)  //可能会无法到达KCF 
    				min1=min(min1,dy[i][j]+dm[i][j]);
    			}
    		}
    		printf("%d\n",min1);
       }
    	return 0;
    }