C/C++教程

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的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!