POJ-3026 Borg Maze

POJ-3026 Borg Maze.cpp

//By Brickgao
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

typedef struct pos{
	int x, y;
	int step;
} pos;
pos p[120];
char amap[120][120];
bool vis[120], visit[120][120];
long long n, x, y, k, ans, map[120][120], dist[120], num[120][120];
long long add[4][2] = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};

void bfs(pos k)
{
	int i, xx, yy, nx, ny, step;
	pos p;
	queue <pos> que;
	memset(visit, false, sizeof(visit));
	que.push(k);
	visit[k.x][k.y] = true;
	while(!que.empty())
	{
		p = que.front();
		que.pop();
		xx = p.x;
		yy = p.y;
		step = p.step + 1;
		for(i = 0; i < 4; i++)
		{
			nx = xx + add[i][0];
			ny = yy + add[i][1];
			if(nx < x && nx >= 0 && ny < y && ny >= 0 && !visit[nx][ny])
			{
				if(amap[nx][ny] == 'S' || amap[nx][ny] == 'A')
				{
					map[num[k.x][k.y]][num[nx][ny]] = map[num[nx][ny]][num[k.x][k.y]] = step;
					p.x = nx;
					p.y = ny;
					p.step = step;
					que.push(p);
					visit[nx][ny] = true;
				}
				if(amap[nx][ny] == ' ')
				{
					p.x = nx;
					p.y = ny;
					p.step = step;
					que.push(p);
					visit[nx][ny] = true;
				}
			}
		}
	}
}

void prim(long long u)
{
	long long i, j, min, tmp;
	for(i = 1; i <= k; i++)
	{
		dist[i] = map[u][i];
		vis[i] = false;
	}
	vis[u] = true;
	tmp = u;
	for(i = 1; i <= k; i++)
	{
		min = 0x7FFFFFFF;
		for(j = 1; j <= k; j++)
			if(!vis[j] && min > dist[j])
			{
				tmp = j;
				min = dist[j];
			}
		if(min != 0x7FFFFFFF)
			ans += min;
		vis[tmp] = true;
		for(j = 1; j <= k; j++)
			if(!vis[j] && dist[j] > map[tmp][j])
				dist[j] = map[tmp][j];
	}
	return;
}

int main()
{
	long long i, j;
	char tmp;
	scanf("%lld", &n);
	while(n--)
	{
		k = 1;
		tmp = ' ';
		scanf("%lld%lld", &x, &y);
		while(tmp != '\n')
			tmp = getchar();
		for(j = 1; j <= y; j++)
		{
			for(i = 1; i <= x; i++)
			{
				tmp = getchar();
				amap[i][j] = tmp;
				if(tmp == 'A' || tmp == 'S')
				{
					p[k].x = i;
					p[k].y = j;
					p[k].step = 0;
					num[i][j] = k;
					k++;
				}
			}
			getchar();
		}
		k--;
		for(i = 1; i <= k; i++)
			bfs(p[i]);
		ans = 0;
		prim(1);
		printf("%lld\n", ans);
	}
    return 0;
}