POJ 3026 Borg Maze(BFS+Kruskal)(***题)

题意就是一个图，然后问从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;
}