题目链接:http://poj.org/problem?id=3026
题意就是一个图,然后问从S开始,遍历每个A的最短距离
这道题不是一般的坑,先说一下思路,我们对于每一个A和S跑一遍BFS,用来求当前点到所有A和S的最短距离当两点间的权值存起来,然后再跑一遍最小生成树就好了。坑点是图是m*n的不是n*m,还有数组要开大,还有就是在输入m*n后面,还有多余的空格,需要一个gets来清除一下。
AC代码:
// #include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <algorithm>
#define maxn 105
using namespace std;
struct Node{
int x,y,w;
bool operator < (const Node &a) const {
return a.w > w;
}
}Edge[maxn * maxn];
struct node{
int x,y,step;
}S,Now,Next;
int pre[maxn * maxn],num;
int id[maxn][maxn];
bool vis[maxn][maxn];
int dir[4][2] = {1,0,0,1,-1,0,0,-1};
char str[maxn][maxn];
int T,n,m;
void init(){
for(int i=0;i<=maxn * maxn;i++) pre[i] = i;
num = 0;
}
void add(int u,int v,int w){
Edge[num].x = u;
Edge[num].y = v;
Edge[num++].w = w;
}
bool Check(int xx, int yy){
if(vis[xx][yy] == true)return false;
if(xx >= 0 && yy >= 0 && xx < n && yy < m && str[xx][yy] != '#')return true;
return false;
}
int Find(int x){
if(x != pre[x]) pre[x] = Find(pre[x]);
return pre[x];
}
void bfs(int x,int y){
memset(vis,false,sizeof(vis));
S.x = x; S.y = y;
S.step = 0;
queue<node> q;
q.push(S);
while(!q.empty()){
Now = q.front();
q.pop();
if(str[Now.x][Now.y] == 'A' || str[Now.x][Now.y] == 'S'){
add(id[x][y], id[Now.x][Now.y], Now.step);
}
for(int i=0;i<4;i++){
Next.x = Now.x + dir[i][0];
Next.y = Now.y + dir[i][1];
if(Check(Next.x, Next.y)){
Next.step = Now.step + 1;
vis[Next.x][Next.y] = 1;
q.push(Next);
}
}
}
}
int Kruskal(){
int sum = 0;
sort(Edge, Edge + num);
for(int i=0;i<num;i++){
if(Find(Edge[i].x) != Find(Edge[i].y)){
pre[Find(Edge[i].y)] = Find(Edge[i].x);
sum += Edge[i].w;
}
}
return sum;
}
int main()
{
char ch[15];
scanf("%d",&T);
while(T--){
init();
scanf("%d %d",&m,&n);
gets(ch);
int cnt = 1;
for(int i=0;i<n;i++){
gets(str[i]);
for(int j=0;j<m;j++){
if(str[i][j] == 'A' || str[i][j] == 'S'){
id[i][j] = cnt ++;
}
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(str[i][j] == 'A' || str[i][j] == 'S'){
bfs(i, j);
}
}
}
printf("%d\n",Kruskal());
}
return 0;
}