POJ 3026 Borg Maze(BFS+prim)
3481 ワード
転送ゲート:http://poj.org/problem?id=3026
この問題の意味は比較的に複雑で、Sから出発して、すべてのA点まで歩いて、すべての点ですべて複数を分裂することができて、つまり、私達はS点も1つのA点と見なすことができて、1つのA点から出発して、すべてのA点がつながっている経路の中でいくつかの経路を選んで、歩いた道を最小にして、問題の意味を簡略化して、実は1つの最小生成木で、しかし、各点間の距離はあらかじめ処理しておく必要がありますが、すべての距離が求められているので、稠密図なのでprimを使ったほうがいいでしょう(kruskalがもっと速くなるかどうか分かりません).
この問題の入力も少し穴があいていて、図の中にスペースが現れて、%sは使えないので、fgetsを使って文字列から内容を読みました.A番号ごとに1つのmapで番号を記録するため、距離と番号の処理が終わると簡単なprimになりますが、最小生成ツリーなので、S点から始める必要もなく、適当に点を選んでprimが終わると完成します.
この問題の構想はやはりとても重要で、問題の長いのも最小の生成木ではありませんて、とても良い問題です!
コード:
この問題の意味は比較的に複雑で、Sから出発して、すべてのA点まで歩いて、すべての点ですべて複数を分裂することができて、つまり、私達はS点も1つのA点と見なすことができて、1つのA点から出発して、すべてのA点がつながっている経路の中でいくつかの経路を選んで、歩いた道を最小にして、問題の意味を簡略化して、実は1つの最小生成木で、しかし、各点間の距離はあらかじめ処理しておく必要がありますが、すべての距離が求められているので、稠密図なのでprimを使ったほうがいいでしょう(kruskalがもっと速くなるかどうか分かりません).
この問題の入力も少し穴があいていて、図の中にスペースが現れて、%sは使えないので、fgetsを使って文字列から内容を読みました.A番号ごとに1つのmapで番号を記録するため、距離と番号の処理が終わると簡単なprimになりますが、最小生成ツリーなので、S点から始める必要もなく、適当に点を選んでprimが終わると完成します.
この問題の構想はやはりとても重要で、問題の長いのも最小の生成木ではありませんて、とても良い問題です!
コード:
#include<stdio.h>
#include<string.h>
#include<ctype.h>
#include<time.h>
#include<vector>
#include<string>
#include<queue>
#include<map>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int INF = 999999999;
int n, m;
char input[300];
char pic[60][60];
int dis[110][110];
int go[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
int d[110];
struct pos {
int x, y;
bool operator < (pos a)
const {
if (x != a.x)
return x < a.x;
return y < a.y;
}
pos(int a, int b) :x(a), y(b) {}
};
struct node{
int x,y,step;
};
int cnt;
map<pos, int> id;
vector<pos> point;
bool judge(int x,int y)
{
return x >= 0 && x < n&&y >= 0 && y < m;
}
int ID(pos x)
{
if (id.count(x))
return id[x];
cnt++;
return id[x] = cnt;
}
void init()
{
memset(dis, 0, sizeof(dis));
cnt = 0;
id.clear();
point.clear();
}
void BFS(int _x, int _y, int st)
{
bool vis[55][55] = {false};
queue<node> Q;
node start, use;
start.step = 0;
start.x = _x;
start.y = _y;
vis[_x][_y] = true;
Q.push(start);
while (!Q.empty())
{
start = Q.front();
Q.pop();
use.step = start.step + 1;
for (int i = 0; i < 4; i++)
{
use.x = start.x + go[i][0];
use.y = start.y + go[i][1];
if (judge(use.x, use.y) && pic[use.x][use.y] != '#'&&vis[use.x][use.y]==false)
{
vis[use.x][use.y] = true;
if (pic[use.x][use.y] == 'A' || pic[use.x][use.y] == 'S')//
{
dis[st][ID(pos(use.x, use.y))] = use.step;
}
Q.push(use);
}
}
}
}
void prim()
{
int ans = 0;
int i, j;
cnt++;// 【1-cnt】 , +1 【1,cnt)
for (i = 2; i < cnt; i++)
{
d[i] = dis[1][i];
}
d[1] = -1;
for (i = 2; i < cnt; i++)// cnt+1 , cnt-2
{
int minn = INF;
int v = -1;
for (j = 2; j < cnt; j++)
{
if (d[j] != -1 && d[j] < minn)
{
minn = d[j];
v = j;
}
}
ans += minn;
d[v] = -1;
for (j = 2; j < cnt; j++)
{
if (dis[v][j] < d[j])
d[j] = dis[v][j];
}
}
printf("%d
", ans);
}
int main()
{
// freopen("D://input.txt", "r", stdin);
// freopen("D://output.txt", "w", stdout);
int T;
scanf("%d", &T);
getchar();
while (T--)
{
init();
int i, j, k;
fgets(input, 300, stdin);
sscanf(input, "%d%d", &m, &n);
for (i = 0; i < n; i++)
{
fgets(input, 300, stdin);
for (j = 0; j < m; j++) {
pic[i][j] = input[j];
if (input[j] == 'A' || input[j] == 'S')// S A , vector
{
point.push_back(pos(i, j));
}
}
}
for (k = 0; k < point.size(); k++)// S A BFS
{
BFS(point[k].x, point[k].y, ID(point[k]));
}
prim();
}
// printf("%.6f
", (double)clock() / CLOCKS_PER_SEC);
return 0;
}