admin 管理员组

文章数量: 1184232

UVALive

题意：求一个房间出发，遍历所有指定房间的最短路


由于指定房间的数量特别少（不超过4），枚举其排列。对每个指定房间求出去其余指定房间的最短路（用bfs），然后根据排列来计算最短路径。


#include <iostream>
#include<bits/stdc++.h>using namespace std;
const int INF=11100000;
const int N=110;
int dir[4][2]={1,0,-1,0,0,1,0,-1};
char s[N][N];
int a[N],bx,by,ans,xx[N],yy[N],k,n,m,v[N][N],mp[N][N];
struct node
{int x,y,sum;
};int main()
{while(~scanf("%d%d",&n,&m)&&(n||m)){for(int i=0;i<n;i++){scanf("%s",s[i]);for(int j=0;j<m;j++){if(s[i][j]=='@'){xx[0]=i;yy[0]=j;}}}scanf("%d",&k);for(int i=1;i<=k;i++){scanf("%d%d",&xx[i],&yy[i]);xx[i]--;yy[i]--;}for(int i=1;i<=k;i++)   a[i]=i;ans=INF;memset(mp,-1,sizeof(mp));for(int j=0;j<=k;j++){memset(v,0,sizeof(v));node t;t.x=xx[j];t.y=yy[j];t.sum=0;v[t.x][t.y]=1;queue<node>q;q.push(t);while(!q.empty()){node t=q.front();q.pop();for(int i=0;i<=k;i++){if(t.x==xx[i]&&t.y==yy[i]){mp[j][i]=t.sum;}}for(int i=0;i<4;i++){int tx=t.x+dir[i][0],ty=t.y+dir[i][1];if(tx<0||tx>=n||ty<0||ty>=m||s[tx][ty]=='#'||v[tx][ty]==1)    continue;v[tx][ty]=1;node tt=t;tt.x=tx;tt.y=ty;tt.sum=t.sum+1;q.push(tt);}}}do{int sum=0,flag=0;for(int i=1;i<=k;i++){if(mp[a[i-1]][a[i]]==-1){flag=1;break;}sum+=mp[a[i-1]][a[i]];}if(flag)    continue;ans=min(sum,ans);}while(next_permutation(a+1,a+k+1));if(ans>=INF)    printf("-1\n");else    printf("%d\n",ans);}
}


本文标签： UVALive

版权声明：本文标题：UVALive 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://roclinux.cn/p/1699249889a338673.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。