[BFS广搜]迷阵
描述
小Z每年都会为程设课出一道大作业，荼毒学弟学妹，可谓罪大恶极不可饶恕。
终于有一天，神明也看不下去了，他唤醒上古四大神兽，决定围困小Z，威慑一番。
于是，在小Z下一次醒来时，他便发现自己已然身处不知名的所在，抬眼所见，只有滚滚迷雾席卷而来，雾霭深处还隐隐约约闪着雷光。
低头一看，地上有一红漆木盒，上书四个大字“求生之道”，打开一看，竟是一台电脑。
电脑上空荡荡的，只有三个文件，一个是 Visual Studio 的安装包，一个是 README.txt，还有一个是 map.png。
小Z想都没想就开始安装 VS，在漫长的等待中，他打开了 README.txt：
“汝罪大恶极，故略施薄惩。此乃四象迷阵，有神兽镇守，踏错一步，险象环生。如欲得生，须观 map.png，寻得最短出路。”
迷阵是 m 行 n 列的格子矩阵，行、列从 1 开始数。小Z出生在左上角，也就是第 1 行，第 1 列的格子，迷阵的出口在第 m 行，第 n 列。
迷阵中有三种格子：
1. 空格子，以英文句点'.'记。出生点和出口都是空格子。
2. 墙，以井号'#'记。小Z无法移动到墙上。
3. 陷阱，以星号'*'记。小Z移动到陷阱的瞬间会受到来自上古神兽的 1 点伤害（生命 - 1），但是离开陷阱的瞬间不会再受到伤害。
小Z的生命有 H 点，当生命到 0 的瞬间他就会被传送回出生点。
小Z的每次行动是向上下左右的四个方向之一移动一格。不能移动出界，不能移动到墙上，但是可以移动到陷阱上。
小Z需要在短短3个小时内写出程序，算出自己最少要走多少步才能走到出口。
但凡迷阵，必有生门。题目保证必定存在一条路径使得小Z能够走到出口。
输入
第一行是一个整数 T，表示输入包含 T 组数据，分别是不同的平行时空下小Z所处的迷阵。
对于每组数据，第一行包括三个整数：m（2 <= m <= 255）、n（2 <= n <= 255）、H（1 <= H <= 5）。
接下来 m 行，每行是一个由符号组成的长度为 n 的字符串，第 i 行的第 j 个字符表示矩阵中第 i 行第 j 列的格子的类型。
题目保证出生点和出口（左上角和右下角）都是空格子。
输出
对于每组数据，你需要输出一行一个正整数，表示小Z在这个迷阵中最少要走多少步才能走到出口。
题目保证小Z一定能走到出口。
样例输入
2 2 2 3 .* #. 5 5 3 ..... ****. ..... .**** .....
样例输出
2 8
解题分析
很经典的广搜题加上了一定的限制条件，所以我们也相应地给visited数组多加上一点维度来判断是否经过。由于多次吃亏，我们还是决定在放入数组的那个时候直接标记visited，避免扩展无用节点导致memory limited exceed！！然后，如果生命值归0了，说明这个路径是不行的，我们也不用继续放进队列扩展了，然后如果说现在的步数已经比答案要更大了，也没有必要放进去，这种减枝是很有效的。
代码实现
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
using namespace std;
int m,n,H;
char maze[260][260];
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
bool visited[260][260][6];struct Node{int x,y,H;int step;Node(int a=0,int b=0,int c=0,int d=0) : x(a),y(b),H(c),step(d) {}
};int main(){int T;scanf("%d",&T);while(T--){memset(visited,0,sizeof(visited));scanf("%d%d%d",&m,&n,&H);for(int i=1;i<=m;i++)for(int j=1;j<=n;j++){scanf(" %c",&maze[i][j]);}int ans=1e9;queue<Node> q;q.push({1,1,H,0});while(!q.empty()){Node tmp=q.front();q.pop();if(tmp.x==m && tmp.y==n){ans=min(ans,tmp.step);break;}for(int i=0;i<4;i++){int x1=tmp.x+dx[i];int y1=tmp.y+dy[i];if(x1>=1 && x1<=m && y1>=1 && y1<=n && maze[x1][y1]!='#'){int tmph=tmp.H;if(maze[x1][y1]=='*') tmph-=1;if(tmph && visited[x1][y1][tmph]==0 && tmp.step+1<ans){q.push({x1,y1,tmph,tmp.step+1});visited[x1][y1][tmph]=1;}} }}printf("%d\n",ans);}return 0;
}