ACM-ICPC寒假算法训练1：搜索专题 Nightmare

本文主要是介绍ACM-ICPC寒假算法训练1：搜索专题 Nightmare，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

HDOJ 1072 Nightmare

题目解析：

这题说，你从起点出发，能不能在炸弹爆炸之前走出终点？炸弹爆炸时间为6分钟，如果你能够在时间变成0之前走出去，你就胜利了！你每次只能朝着上下左右四个方向走，走一步需要1分钟，问你最短需要多久才能走出去？这里很有意思的是还有时间重置设备，如果你碰到这个设备，可以让炸弹的时间重新回到6分钟。

算法分析：

这题是问你最短需要多久，在这种不带权的图中，求最短路径，就是用bfs去做，但是这题有个6分钟的时间限制，这样与普通的最短路问题就有区别。区别在于，普通的最短路，bfs的结果一定保证是最优解，因为宽度优先，先碰到的节点一定是较快碰到的；然而，如果我们要在规定时间内去走最短路，加上有个重置装置，我们如果能够在6分钟内走出去，那么bfs的答案就是最优解，但是如果6分钟走不出去，那么就需要考虑是不是要先走到一个时间重置的装置那里去，然后再想办法走出去！

可是，这样的区别，我们该怎样去设计算法和编码呢？？
它的规则：这两点尤其需要注意

思考：

既然这个图中的点可以重复去走，那么时间重置的点是否可以重复去走呢？可以！但没必要，因为你到达一个重置点之后，往哪走都一样，如果你还回头去走那个重置点，步数必然会增加而且时间上效果没有发生变化。也就是说，如果你经过一个重置点，还是走不出去或者走不到下一个重置点，就算是你走回头路也是没用的，反之如果能走出去或者到下一个重置点，那你完全没有必要再走一遍。

Solving code：

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int maxn = 10;
int t, n, m, mp[maxn][maxn];
int dir[4][2] = { {0, 1},{0, -1},{1, 0},{-1, 0} };
struct Point {
	int x, y, step, time;
}Begin, Now, Next;
int bfs() {
	queue<Point> q;
	q.push(Begin);
	while (!q.empty()) {
		Now = q.front(); q.pop();
		if (1 == Now.time)	continue;
		for (int i = 0; i < 4; i++) {
			Next.x = Now.x + dir[i][0], Next.y = Now.y + dir[i][1];
			if (Next.x >= 0 && Next.x < n && Next.y >= 0 && Next.y < m && mp[Next.x][Next.y]) {
				Next.step = Now.step + 1, Next.time = Now.time - 1;
				if (3 == mp[Next.x][Next.y])	return Next.step;
				if (4 == mp[Next.x][Next.y]) {
					Next.time = 6;
					mp[Next.x][Next.y] = 0;
				}
				q.push(Next);
			}
		}
	}
	return -1;
}

int main() {
	scanf("%d", &t);
	while (t--) {
		scanf("%d %d", &n, &m);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				scanf("%d", &mp[i][j]);
				if (2 == mp[i][j]) {
					Begin.x = i, Begin.y = j;
					Begin.step = 0, Begin.time = 6;
				}
			}
		}
		printf("%d\n", bfs());
	}
	return 0;
}

这篇关于ACM-ICPC寒假算法训练1：搜索专题 Nightmare的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！