Stealing Harry Potter's Precious BFS+DFS
Some rooms are indestructible and some rooms are vulnerable. Goblins always care more about their own safety than their customers' properties, so they live in the indestructible rooms and put customers' properties in vulnerable rooms. Harry Potter's precious are also put in some vulnerable rooms. Dudely wants to steal Harry's things this holiday. He gets the most advanced drilling machine from his father, uncle Vernon, and drills into the bank. But he can only pass though the vulnerable rooms. He can't access the indestructible rooms. He starts from a certain vulnerable room, and then moves in four directions: north, east, south and west. Dudely knows where Harry's precious are. He wants to collect all Harry's precious by as less steps as possible. Moving from one room to another adjacent room is called a 'step'. Dudely doesn't want to get out of the bank before he collects all Harry's things. Dudely is stupid.He pay you $1,000,000 to figure out at least how many steps he must take to get all Harry's precious.
In each test cases:
The first line are two integers N and M, meaning that the bank is a N × M grid(0<N,M <= 100).
Then a N×M matrix follows. Each element is a letter standing for a room. '#' means a indestructible room, '.' means a vulnerable room, and the only '@' means the vulnerable room from which Dudely starts to move.
The next line is an integer K ( 0 < K <= 4), indicating there are K Harry Potter's precious in the bank.
In next K lines, each line describes the position of a Harry Potter's precious by two integers X and Y, meaning that there is a precious in room (X,Y).
The input ends with N = 0 and M = 0
##@
#.#
1
2 2
4 4
#@##
....
####
....
2
2 1
2 4
0 0
5
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<cstring>
#include<iostream>
#define MAXN 102
#define INF 0x3f3f3f3f
#define eps 1e-11 + 1e-12/2
typedef long long LL; using namespace std;
/*
BFS + 最小生成树
*/
char g[MAXN][MAXN];
bool vis[MAXN][MAXN];
int step[MAXN][MAXN];
int map[MAXN][MAXN];
struct node
{
node(int _x, int _y, int _t) :x(_x), y(_y), t(_t) {}
int x, y, t;
};
vector<node> v;
int x[] = { ,-,, };
int y[] = { ,,,- };
int tx, ty, n, m, k, ans;
void bfs(int sx,int sy)
{
queue<node> q;
vis[sx][sy] = true;
step[sx][sy] = ;
q.push(node(sx, sy, ));
while (!q.empty())
{
node t = q.front();
q.pop();
for (int i = ; i < ; i++)
{
int nx = t.x + x[i], ny = t.y + y[i];
if (nx >= && ny >= && nx < n&&ny < m && !vis[nx][ny] && g[nx][ny] != '#')
{
vis[nx][ny] = true;
step[nx][ny] = t.t + ;
q.push(node(nx, ny, t.t + ));
}
}
}
}
void dfs(int cnt, int k, int sum)
{
if (cnt == v.size())
{
ans = min(sum, ans);
return;
}
for (int i = ; i < v.size(); i++)
{
if (!vis[][i])
{
vis[][i] = true;
dfs(cnt + , i, sum + map[k][i]);
vis[][i] = false;
}
} }
int main()
{
while (scanf("%d%d", &n, &m), n + m)
{
v.clear();
ans = INF;
for (int i = ; i < n; i++)
{
scanf("%s", g[i]);
for (int j = ; j < m; j++)
if (g[i][j] == '@')
v.push_back(node(i, j, -));
}
scanf("%d", &k);
for (int i = ; i < k; i++)
{
scanf("%d%d", &tx, &ty);
v.push_back(node(tx - , ty - , -));
}
for (int i = ; i < v.size(); i++)
{
memset(step, INF, sizeof(step));
memset(vis, false, sizeof(vis));
bfs(v[i].x, v[i].y);
for (int j = ; j < v.size(); j++)
if (step[v[j].x][v[j].y] != INF)
map[i][j] = step[v[j].x][v[j].y];
else
map[i][j] = INF;
}
int ck = ;
for (ck = ; ck < v.size(); ck++)
if (map[v[ck].x][v[ck].y] == INF)
break;
if (ck != v.size())
{
printf("-1\n");
continue;
}
memset(vis, false, sizeof(vis));
vis[][] = true;
dfs(, , );
if (ans != INF)
printf("%d\n", ans);
else
printf("-1\n");
}
}
最新文章
- JavaScript 中的数据类型
- css3的背景颜色渐变@线性渐变
- 为Autodesk Viewer添加自定义工具条
- 百度Site App的uaredirect.js实现手机访问,自动跳转网站手机版
- zoj 2112 Dynamic Rankings 动态第k大 线段树套Treap
- JavaScript—W3school
- VS(Microsoft Visual Studio2010)工具打开项目所需的应用程序,出现未安装(.csproj)的应用程序的解决办法
- HDOJ1166 敌兵布阵
- poj2070简单题
- MarkDown使用 (三)表格
- Pycharm安装、设置、优化
- 前端之 HTML&#127875;
- 比较Fink, macports 跟 homebrew
- luogu P2325 [SCOI2005]王室联邦
- cookie和session的比较
- mkdir 权限值注意要用八进制表示,即“0”开头,而且一定不要加引号http://php.net/manual/en/function.mkdir.php
- js oc与线程
- 变分自编码器(Variational auto-encoder,VAE)
- hdu 1213 How Many Tables(并查集算法)
- 《挑战程序设计竞赛》2.2 贪心法-其它 POJ3617 3069 3253 2393 1017 3040 1862 3262
热门文章
- TFS修改了工作区
- .net环境下程序一些未知错误的调试
- [ SPOJ Qtree1 ] Query on a tree
- Selenium常用方法及函数
- JavaScript 单例,Hash,抛异常
- [Tensorflow] 使用 model.save_weights() 保存 Keras Subclassed Model
- .net core Elasticsearch 查询更新
- The method buildSessionFactory() from the type Configuration is deprecated.SessionFactory的变化
- JavaScript--小白入门篇1
- Gym - 101670J Punching Power(CTU Open Contest 2017 最大独立集)