题目链接:
https://vjudge.net/problem/POJ-3026
题目大意:
在一个y行 x列的迷宫中,有可行走的通路空格’ ‘,不可行走的墙’#’,还有两种英文字母A和S,现在从S出发,要求用最短的路径L连接所有字母,输出这条路径L的总长度。
思路:
先BFS预处理出所有的字母之间的距离,然后用prim模板
超级坑的是这里得用gets()吃掉回车符,用getchar()会WA
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<sstream>
using namespace std;
typedef long long ll;
typedef pair<int, int> Pair;
const int maxn = 1e2 + ;
const int INF = 0x3f3f3f3f;
int dir[][] = {,,,,-,,,-};
int T, n, m, x;
int Map[maxn][maxn];//存图
int lowcost[maxn], mst[maxn];
void prim(int u, int n)//最小生成树起点
{
int sum_mst = ;//最小生成树权值
for(int i = ; i < n; i++)//初始化两个数组
{
lowcost[i] = Map[u][i];
mst[i] = u;
}
mst[u] = -;//设置成-1表示已经加入mst
for(int i = ; i < n; i++)
{
int minn = INF;
int v = -;
//在lowcost数组中寻找未加入mst的最小值
for(int j = ; j < n; j++)
{
if(mst[j] != - && lowcost[j] < minn)
{
v = j;
minn = lowcost[j];
}
}
if(v != -)//v=-1表示未找到最小的边,
{//v表示当前距离mst最短的点
//printf("%d %d %d\n", mst[v], v, lowcost[v]);//输出路径
mst[v] = -;
sum_mst += lowcost[v];
for(int j = ; j < n; j++)//更新最短边
{
if(mst[j] != - && lowcost[j] > Map[v][j])
{
lowcost[j] = Map[v][j];
mst[j] = v;
}
}
}
}
//printf("weight of mst is %d\n", sum_mst);
cout<<sum_mst<<endl;
}
string s[];
vector<Pair>a;
int vis[][];
void bfs(int u, int x, int y)//BFS预处理,将x,y为起点进行遍历,求出每个点离当前点距离,更新出Map距离出来
{
queue<Pair>q;
q.push(Pair(x, y)); memset(vis, -, sizeof(vis));
vis[x][y] = ;
while(!q.empty())
{
Pair now = q.front();
q.pop();
for(int i = ; i < ; i++)
{
int xx = now.first + dir[i][];
int yy = now.second + dir[i][];
if(xx >= && xx < n && yy >= && yy < m && s[xx][yy] != '#' && vis[xx][yy] == -)
{
vis[xx][yy] = vis[now.first][now.second] + ;
q.push(Pair(xx, yy));
}
}
}/*
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)cout<<vis[i][j]<<" ";
cout<<endl;
}*/
for(int i = ; i < a.size(); i++)
{
if(i == u)continue;
Map[u][i] = vis[a[i].first][a[i].second];
}
}
int main()
{
cin >> T;
getchar();
while(T--)
{
for(int i = ; i < ; i++)s[i].clear();
char cc[];
cin >> m >> n;
gets(cc);
a.clear();
for(int i = ; i < n; i++)
{
getline(cin, s[i]);
for(int j = ; j < m; j++)
if(s[i][j] == 'S' || s[i][j] == 'A')
a.push_back(Pair(i, j));
}
for(int i = ; i < a.size(); i++)
{
for(int j = ; j < a.size(); j++)
{
if(i == j)Map[i][j] = ;
else Map[i][j] = INF;
}
}
for(int i = ; i < a.size(); i++)
bfs(i, a[i].first, a[i].second);
/*for(int i = 0; i < a.size(); i++)
{
for(int j = 0; j < a.size(); j++)
{
cout<<Map[i][j]<<" ";
}
cout<<endl;
}*/
prim(, a.size());
}
return ;
}
POJ-3026 Borg Maze---BFS预处理+最小生成树的更多相关文章
-
POJ - 3026 Borg Maze BFS加最小生成树
Borg Maze 题意: 题目我一开始一直读不懂.有一个会分身的人,要在一个地图中踩到所有的A,这个人可以在出发地或者A点任意分身,问最少要走几步,这个人可以踩遍地图中所有的A点. 思路: 感觉就算 ...
-
poj 3026 Borg Maze (BFS + Prim)
http://poj.org/problem?id=3026 Borg Maze Time Limit:1000MS Memory Limit:65536KB 64bit IO For ...
-
poj 3026 Borg Maze (bfs + 最小生成树)
链接:poj 3026 题意:y行x列的迷宫中,#代表阻隔墙(不可走).空格代表空位(可走).S代表搜索起点(可走),A代表目的地(可走),如今要从S出发,每次可上下左右移动一格到可走的地方.求到达全 ...
-
poj 3026 Borg Maze bfs建图+最小生成树
题目说从S开始,在S或者A的地方可以分裂前进. 想一想后发现就是求一颗最小生成树. 首先bfs预处理得到每两点之间的距离,我的程序用map做了一个映射,将每个点的坐标映射到1-n上,这样建图比较方便. ...
-
POJ - 3026 Borg Maze bfs+最小生成树。
http://poj.org/problem?id=3026 题意:给你一个迷宫,里面有 ‘S’起点,‘A’标记,‘#’墙壁,‘ ’空地.求从S出发,经过所有A所需要的最短路.你有一个特殊能力,当走到 ...
-
POJ 3026 Borg Maze bfs+Kruskal
题目链接:http://poj.org/problem?id=3026 感觉英语比题目本身难,其实就是个最小生成树,不过要先bfs算出任意两点的权值. #include <stdio.h> ...
-
POJ 3026 Borg Maze【BFS+最小生成树】
链接: http://poj.org/problem?id=3026 http://acm.hust.edu.cn/vjudge/contest/view.action?cid=22010#probl ...
-
POJ 3026 Borg Maze(bfs+最小生成树)
Borg Maze Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 6634 Accepted: 2240 Descrip ...
-
快速切题 poj 3026 Borg Maze 最小生成树+bfs prim算法 难度:0
Borg Maze Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 8905 Accepted: 2969 Descrip ...
-
POJ 3026 --Borg Maze(bfs,最小生成树,英语题意题,卡格式)
Borg Maze Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 16625 Accepted: 5383 Descri ...
随机推荐
-
xss之渗透测试
跨站脚本攻击:cross site script execution(通常简写为xss,因css与层叠样式表同名,故改为xss),是指攻击者利用网站程序对用户输入过滤不足,输入可以显示在页面上对其他用 ...
-
CDDA 源码解析
一.编译1:从 https://github.com/CleverRaven/Cataclysm-DDA 下载源码2:下载IDE CodeBlocks,http://pan.baidu.com/s/1 ...
-
OSG模型简单控制
OSG模型简单控制 转自:http://milkcu.sintune.net/blog/archives/1392673560.html 结点基本操作 添加结点 OSG中使用osg::Node和osg ...
-
.net下的跨域问题
环境: IIS7.0 MVC 4.0 公司官网 asp.net 需要的报名系统,需要有后台管理 由于是配合传统产业,所以MVC系统的数据,是由AIPS系统提供. (制作前是考虑去年用 ...
-
shell定时任务
1.认识Croncron是一个linux下的定时执行工具,可以在无需人工干预的情况下运行作业.由于Cron 是Linux的内置服务,但它不自动起来,可以用以下的方法启动.关闭这个服务:/sbin/se ...
-
dubbo子模块
dubbo源码版本:2.5.4 经统计,dubbo一共有36个子模块,子模块如下: ---------------------------------------------------------- ...
-
判断HTML中的checkbox是否被选中
//合法性验证 function checkValidity() { var userNameCheck = $("#userNameCheck").attr('checked') ...
-
struts2简单入门-配置文件-struts.xml
struts.xml 作用:配置struts中的action,result,package,全局action,result,等等. 基本文件格式: <?xml version="1.0 ...
-
ubuntu16.04 ROS环境下配置和运行SVO
ubuntu16.04 ROS环境下配置和运行SVO https://blog.csdn.net/nnUyi/article/details/78005552
-
在SQL Server中用好模糊查询指令LIKE (转载)
like在sql中的使用:在SQL Server中用好模糊查询指令LIKE:查询是SQL Server中重要的功能,而在查询中将Like用上,可以搜索到一些意想不到的结果和效果,like的神奇 一.一 ...