UVA1601 The Morning after Halloween

UVA1601 The Morning after Halloween

题目链接

做这道题的时候看到一个写的很好的代码，在这里保存下来，以便以后学习。

题目分析

这道题和普通的bfs有所不同，解题方法也有些差别，主要是这里有三个移动的“小鬼”，每个小鬼有五种移动状态（上下左右和不动），最主要的是可以看出在地图上大部分的点都是障碍物，所以可以把所有的空格都提出来建立一张图，而不必每次判断五种方法是否合法，以此来优化算法。

代码解析

本题代码中用到的变量较多，为便于理解，先把主要变量的含义解释一下。

x[i] :第i个空格的横坐标 y[i] :第i个空格的纵坐标 id[i][j] :坐标为(i,j)的空格的编号 s[i]:初始小鬼所在空格的编号 t[i]:小鬼所要到达的目标位置的空格编号 deg[i]:在第i个空格所能走的步数 G[i][j]:在第i个空格所能到达的第j个位置的空格编号

注意事项： main函数中最后两个if语句的作用是当小鬼的数量小于三个时，默认多出的小鬼初始位置即为目标位置，且他们只能原地不动。 ID函数的作用是将三个变量合成一个变量一次性存到队列中。

#define _CRT_SECURE_NO_WARNINGS
#include 
#include 
#include 
#include 
using namespace std;

int w, h, n, s[3], t[3];
char dataset[20][20];
int G[200][5], vis[200][200][200], dist[200][200][200];
int deg[200];

int dx[] = { 0,-1,1,0,0 };
int dy[] = { 0,0,0,-1,1 };

inline int ID(int a, int b, int c)
{
	return(a  8) & 0xff;
		int c = u & 0xff;
		if (a == t[0] && b == t[1] && c == t[2])
			return dist[a][b][c];
		for (int i = 0; i