HDU 1026 Ignatius and the Princess I 迷宫范围内的搜索剪枝问题

这个问题是一个典型的类型的问题迷宫广泛的搜索。

在网上看到了很多解决方案。

没什么解决问题的分析报告，不指出其中的关键点。代码更像是一大抄。一些分析师也有很大的文章分析。只是不要全部命中关键，什么是广泛而深刻的，甚至搜索发现，在分析差异。为什么快速搜索宽像，什么样的风暴喊搜索，都错了。代码都是抄过的。

通过一大段的时间研究，最终搞通了。

本题尽管能够说是广搜。可是当中的关键却是剪枝法。为什么呢？

由于迷宫并不能简单地广搜就能搜索出全部路径的，甚至仅仅要迷宫大点就不能搜索出是否有路径。假设没有条件剪枝的情况下。不信，你严格写一个广搜搜索一下迷宫路径看看。当然你写了个错误的广搜。自然得出错误的答案了。

常见的错误是一格一格地扩展迷宫就以为是迷宫的广搜了，错！

真正的广搜是须要把迷宫建图。然后广搜。

事实上真正的关键是剪枝：

剪枝思考就是要思考什么时候应该扩展到下一格？是否合法的格子就一定能够扩展？当然不是，是须要依据题意剪枝。本题的题意是求用时最小的路径。故此能够由此想到应该是以时间比較来决定是否须要扩展到下一格的。

即下一格有可能找到更加优的解就扩展。否则就不扩展。

这样一剪枝之后。就能够使用所谓的广搜了。

那么为什么本题。或者能够说本题题型的题目不能够使用深搜呢？

由于上面的剪枝条件是每一层去剪枝的，假设使用深搜，那么这种剪枝条件就无法用上了。

另一种做法就是利用优先队列。优先扩展当前最小用时的格子。那么就能够不用反复搜索下一格了。这也是利用了上面的剪枝思想。

只是仅仅要理解了上面的关键剪枝点，那么这种题目都能够随心所欲地攻克了。

至于本题的记录路径就是编程功底的測试了，不用说什么思路了。不会的仅仅能说编码能力不行了。

或许也有不懂分析的人也把代码敲对了，或许是他运气不错。或许是他真的是天才级的人物！

反正几率都非常低，最大几率还是他的代码是抄来的。

#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <limits.h>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;

/*
关键理解：仅仅有当下一个格子更新了最小值的时候才须要扩展到这个格子。否则就不须要扩展到这个格子。这个也是相当于广搜的剪枝点。

理解不了这点的。就没有透切理解这个问题。
*/
namespace IgnatiusandthePrincessI1026
{

const int MAX_N = 101;
char Maze[MAX_N][MAX_N];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};

struct Node
{
	int sec, x, y;
	Node *p;
};

Node mazeRec[MAX_N][MAX_N];

int N, M;

inline bool isLegal(int r, int c)
{
	return 0<=r && 0<=c && r<N && c<M && Maze[r][c] != 'X';
}

inline int getSec(int r, int c)
{
	if (Maze[r][c] == '.') return 1;
	return Maze[r][c] - '0' + 1;
}

void getPath()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			mazeRec[i][j].sec = INT_MAX;
			mazeRec[i][j].x = i, mazeRec[i][j].y = j;
			mazeRec[i][j].p = NULL;
		}
	}
	queue<Node *> qu;
	Node *p = &mazeRec[N-1][M-1];

	//注意计算错误：p->sec = Maze[N-1][M-1] or = getSec(N-1, M-1)
	p->sec = getSec(N-1, M-1)-1;//终点也可能是有敌人,起点规定了无敌人
	qu.push(p);
	while (!qu.empty())
	{
		p = qu.front(); qu.pop();
		for (int i = 0; i < 4; i++)
		{
			int tx = p->x + dx[i], ty = p->y + dy[i];
			if (!isLegal(tx, ty)) continue;

			int sec = getSec(tx, ty);
			Node *tmp = &mazeRec[tx][ty];

			if (p->sec+sec < tmp->sec)
			{
				tmp->sec = p->sec+sec;
				tmp->p = p;
				qu.push(tmp);
			}
			/*
关键理解：仅仅有当下一个格子更新了最小值的时候才须要扩展到这个格子。否则就不须要扩展到这个格子。这个也是相当于广搜的剪枝点。

理解不了这点的，就没有透切理解这个问题。
*/
/*各种错误教训！
			qu.push(tmp);
			tmp.vis = true;	//错误多个else。逻辑错误else tmp->vis = true

			//Maze[tx][ty] = 'X';
			tmp.sec = p.sec+sec;
			tmp.p = &mazeRec[p.x][p.y];
			
			//错误：tmp->p = p;
			//错误：tmp->sec = min(tmp->sec, p->sec+sec);*/
		}
	}
}

int main()
{
	while (~scanf("%d %d", &N, &M))
	{
		while (getchar() != '
');
		for (int i = 0; i < N; i++)
		{
			gets(Maze[i]);
		}
		getPath();
		Node *p = &mazeRec[0][0];
		if (p->sec == INT_MAX) puts("God please help our poor hero.");
		else
		{
			printf("It takes %d seconds to reach the target position, let me show you the way.
", p->sec);
			int s = 1;
			for (; p->p; p = p->p)
			{
				int x = p->p->x, y = p->p->y;
				printf("%ds:(%d,%d)->(%d,%d)
", s++, p->x, p->y, x, y);
				if (Maze[x][y] == '.') continue;

				int fig = Maze[x][y] - '0';//错误少-'0'
				for (int i = 0; i < fig; i++)
				{
					printf("%ds:FIGHT AT (%d,%d)
", s++, x, y);
				}
			}
		}
		puts("FINISH");
	}
	return 0;
}