POJ - 3062 Borg Maze
题目链接:http://poj.org/problem?id=3026
Svenskt Masterskap我程序员/ Norgesmesterskapet 2001
Description
Your task is to help the Borg (yes, really) by developing a program which helps the Borg to estimate the minimal cost of scanning a maze for the assimilation of aliens hiding in the maze, by moving in north, west, east, and south steps. The tricky thing is that the beginning of the search is conducted by a large group of over 100 individuals. Whenever an alien is assimilated, or at the beginning of the search, the group may split in two or more groups (but their consciousness is still collective.). The cost of searching a maze is definied as the total distance covered by all the groups involved in the search together. That is, if the original group walks five steps, then splits into two groups each walking three steps, the total distance is 11=5+3+3.
Input
Output
Sample Input #####
#A#A##
# # A#
#S ##
##### #####
#AAA###
# A#
# S ###
# #
#AAA###
#####
Sample Output
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#include<math.h>
#include<queue>
#include<map>
using namespace std; #define INF 0x3f3f3f3f
#define N 1200 int n,m,maps[N][N],b[N][N],dist[N],vis[N][N],viss[N];
char s[N][N];
int dir[][]={ {,},{,-},{,},{-,} }; struct node
{
int x,y,step;
}a[N]; void Init()
{
int i,j;
for(i=;i<m*n;i++)
dist[i]=INF;
for(j=;j<n*m;j++)
maps[i][j]=(i==j)?:INF;
} void bfs(int ss,int x,int y)
{
int i; memset(vis,,sizeof(vis));
queue<node>Q;
node B,Next,Now;
B.x=x;
B.y=y;
B.step=;
Q.push(B);
vis[x][y]=; while(Q.size())
{
Now=Q.front();
Q.pop(); if(s[Now.x][Now.y]>='A'&&s[Now.x][Now.y]<='Z')
maps[ss][b[Now.x][Now.y]]=Now.step; for(i=;i<;i++)
{
Next.x=Now.x+dir[i][];
Next.y=Now.y+dir[i][];
if(Next.x<m&&Next.x>=&&Next.y<n&&Next.y>=&&vis[Next.x][Next.y]==&&s[Next.x][Next.y] != '#')
{
vis[Next.x][Next.y]=;
Next.step=Now.step+;
Q.push(Next);
}
}
}
} int Prim(int e)
{
int i,j;
viss[]=;
for(int i=;i<=e;i++)
dist[i]=maps[][i];
int sum=;
for(i=;i<=e;i++)
{
int Min=INF,index=-; for(j=;j<=e;j++)
if(!viss[j]&&Min>dist[j])
{
Min=dist[j];
index=j;
}
if(index==-)break;
sum+=Min;
viss[index]=; for(j=;j<=e;j++)
if(!viss[j]&&dist[j]>maps[index][j])
dist[j]=maps[index][j];
} return sum;
} int main()
{
int T,i,j; scanf("%d", &T); while(T--)
{
memset(a,,sizeof(a));
memset(viss,,sizeof(viss)); scanf("%d%d ", &n,&m);
Init(); int cnt=;
for(i=;i<m;i++)
{
gets(s[i]);
for(j=;j<n;j++)
{
if(s[i][j]<='Z'&&s[i][j]>='A')
b[i][j]=cnt++;///记录cnt号动点位置
}
} for(i=;i<m;i++)
{
for(j=;j<n;j++)
{
if(s[i][j]<='Z'&&s[i][j]>='A')
bfs(b[i][j],i,j);///搜索,记录各个点之间步数
}
} int ans=Prim(cnt-);///最小生成树求最终值
printf("%d\n", ans);
}
}
最新文章
- c++ 注册类到 lua
- C#项目中常用到的设计模式
- .Net资源总结
- 6. javacript高级程序设计-面向对象设计
- UESTC 771 最大容积(前缀后缀和)
- Android开发中的OpenCV霍夫直线检测(Imgproc.HoughLines()&;Imgproc.HoughLinesP())
- [Swift]LeetCode227. 基本计算器 II | Basic Calculator II
- Kubernetes 笔记 04 架构是个好东西
- sub2ind函数
- git 下载部分目录
- AJAX方法讲解
- tomcat 取消项目名访问路径
- docker --alpine包管理工具 --apk
- ios 回调函数作用
- H.264开源解码器评测
- godep 包管理
- java Object类源代码详解 及native (转自 http://blog.csdn.net/sjw890821sjw/article/details/8058843)
- js 使用jquery.form.js文件上传
- QTableWidget的表头颜色设置
- 每天一个linux命令(文件操作):【转载】whiereis命令