http://poj.org/problem?id=3026
如果一个一个普通搜处理不好的话会超时 可以连到一块搜
我觉得这个方法特别好
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<math.h> #include<iostream> #include<queue> #include<algorithm> #define N 105 #define INF 0x3f3f3f3f using namespace std; int dis[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; int G[N][N],d[N],vis[N][N],m,n,v[N],b[N][N]; char F[N][N]; struct node { int x,y,temp; }a; void Inn() { int i,j; for(i=0;i<=N;i++) { d[i]=INF; for(j=1;j<=N;j++) G[i][j]=INF; } memset(b,0,sizeof(b)); memset(F,0,sizeof(F)); } void bfs(int s,int x,int y) { int i; memset(vis,0,sizeof(vis)); queue<node>Q; a.x=x; a.y=y; a.temp=0; Q.push(a); vis[a.x][a.y]=1; while(Q.size()) { node q,p; q=Q.front(); Q.pop(); if(F[q.x][q.y]=='A' || F[q.x][q.y]=='S') G[s][b[q.x][q.y]]=q.temp; for(i=0;i<4;i++) { p.x=q.x+dis[i][0]; p.y=q.y+dis[i][1]; if(F[p.x][p.y]!='#' && p.x<m&&p.y<n&&p.x>=0&&p.y>=0&&!vis[p.x][p.y]) { p.temp=q.temp+1; Q.push(p); vis[p.x][p.y]=1; } } } } int prim(int k) { memset(v,0,sizeof(v)); int i,j,ans=0; for(i=1;i<=k;i++) { d[i]=G[1][i]; } v[1]=1; for(i=1;i<k;i++) { int Min=INF; int dist; for(j=1;j<=k;j++) { if(!v[j] && d[j]<Min) { Min=d[j]; dist=j; } } v[dist]=1; ans+=Min; for(j=1;j<=k;j++) { if(!v[j] && d[j]>G[dist][j]) d[j]=G[dist][j]; } } return ans; } int main() { int T,i,j; scanf("%d",&T); while(T--) { scanf("%d %d ",&n,&m); Inn(); int k=1; for(i=0;i<m;i++) { for(j=0;j<n;j++) { scanf("%c",&F[i][j]); if(F[i][j]=='A' || F[i][j]=='S') { b[i][j]=k; k++; } } getchar(); } for(i=0;i<m;i++) { for(j=0;j<n;j++) { if(F[i][j]=='A' || F[i][j]=='S') bfs(b[i][j],i,j); } } printf("%d ",prim(k-1)); } return 0; }