题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3442
题目大意：三国时期，刘备逃亡。给定一个最大为50*50的地图，刘备在地图中只能往4个方向走。
地图中，A代表瞭望塔，攻击范围是2，攻击伤害是1；
B 代表堡垒，攻击范围是3，攻击伤害是2；
C 代表火焰，对于走在该位置上的单位造成3点伤害；
D 代表弓箭手，攻击范围是2，攻击伤害是4；
E 代表士兵，攻击范围是1，攻击伤害是5；
$ 代表刘备；
! 代表目的地；
# 代表障碍物
. 代表地板
刘备不能穿过A,B,D,E。但是可以走上C和地板。 有3条重要规则：
1.刘备不能被相同的东西伤害2次，比如之前被瞭望塔伤害过，之后再走近瞭望塔的攻击范围时不受伤害。
2.当刘备到达目的地，首先要计算他受到的伤害，然后结束游戏。
3.不需要计算刘备在开始位置受到的伤害。
判断刘备是否可以消耗最少HP，到达目的地，求出最少消耗。
Sample Input
1
4 3
.$.
ACB
ACB
.!.
Sample Output
Case 1: 6
分析：这道题目恶心死我了，之前用map[][],mp[][]两个数组想着方便，结果有一个地方弄错了，那个纠结啊，纠结。看来大牛喜欢长的名字也不是没有道理，起码不会跟其他名称混掉。
题目中的攻击范围（measured by Manhattan distance）是两个点p1(x1,y1),p2(x2,y2)之间，|x1-x2|+|y1-y2|的大小
因为A,B,C,D,E所造成的伤害分别是1,2,3,4,5，而且每种伤害最多只能受一次，所以刘备最多受到1+2+3+4+5点伤害。此时我们可以用二进制中的位数来表示伤害，比如，
01100这个状态就表示刘备收到了C造成的3点伤害和D造成的4点伤害。
这样做的另一个好处就是如果同一个位置受到两种或多种伤害，也可以同时表示出来，互相之间不会干扰。
令dp[i][j][s]表示刘备在(i,j)的位置时，受伤害的状态为s时，HP的最小花费。则答案为终点位置，所有受伤状态里边HP的最小花费。
接下来BFS
代码如下：
# include<cstdio>
# include<cstring>
# include<queue>
# include<cmath>
using namespace std;
const int MAX = ;
char map[MAX][MAX];
int damage[MAX][MAX]; //地图上的每一个位置刘备受到的伤害，如果为-1，表示刘备不能进入该位置
int dp[MAX][MAX][<<];
int dx[] = {,,,-};
int dy[] = {,,-,};
struct node{
int x,y,hp;
}st,u,v; int n, m, sx, sy, ex, ey;
queue<node >q;
bool judge(int x,int y){
if(x>= && x<n &&y>= && y<m && damage[x][y] != )
return true;
return false;
}
void init(){ //将原地图转化成刘备受伤害的地图
int i,j,x,y,bx,by;
memset(damage,,sizeof(damage));
for(i=; i<n; i++){
for(j=; j<m; j++){
if(map[i][j] == '#')
damage[i][j] = -; //不可以踏入 else if(map[i][j] == '$')
sx = i, sy = j; else if(map[i][j] == '!')
ex = i, ey = j; else if(map[i][j] == 'A'){
damage[i][j] = -;
for(x=-; x<; x++){
for(y=-; y<; y++){
if(abs(x) + abs(y) >) continue;
bx = i+x;
by = j+y;
if(judge(bx,by))
damage[bx][by] |= ;
}
}
}
else if(map[i][j]=='B'){
damage[i][j] = -;
for(x=-; x<; x++){
for(y=-; y<; y++){
if(abs(x) + abs(y) > ) continue;
bx = i+x;
by = j+y;
if(judge(bx,by))
damage[bx][by] |= <<;
}
}
}
else if(map[i][j] == 'C')
damage[i][j] |= <<; else if(map[i][j] == 'D'){
damage[i][j] = -;
for(x=-; x<; x++){
for(y=-; y<; y++){
if(abs(x) + abs(y) >) continue;
bx = i+x;
by = j+y;
if(judge(bx,by))
damage[bx][by] |= <<;
}
}
}
else if(map[i][j] == 'E'){
damage[i][j] = -;
for(x=-; x<; x++){
for(y=-; y<; y++){
if(abs(x) + abs(y) >) continue;
bx = i+x;
by = j+y;
if(judge(bx,by))
damage[bx][by] |= <<;
}
}
} }
}
}
int main(){
int T,cas;
int i,j;
scanf("%d",&T);
for(cas=; cas<=T; cas++)
{
scanf("%d%d",&n,&m);
for(i=; i<n; i++)
scanf("%s", map[i]);
init();
st.x = sx;
st.y = sy;
st.hp = ;
memset(dp, -, sizeof(dp));
dp[st.x][st.y][] = ;
//以上为初始化
q.push(st);
int a, b, c;
//BFS
while(!q.empty()){
u = q.front();
q.pop();
for(i=; i<; i++){
b = dp[u.x][u.y][u.hp];
v.x = u.x + dx[i];
v.y = u.y + dy[i];
if(v.x>=n || v.x< || v.y>=m || v.y< ) continue; //不在地图上
if(damage[v.x][v.y] == -) continue; //不能踏入 for(j=; j<; j++){
a = damage[v.x][v.y] & (<<j); //此位置是否有给单位的伤害
c = u.hp & (<<j); //刘备是否已经受过了该单位的伤害
if(a!= && c==)
b += j+; //刘备受到伤害，伤害值为j+1
}
v.hp = u.hp | damage[v.x][v.y]; //经过该点受到的总伤害
if(dp[v.x][v.y][v.hp] == - || dp[v.x][v.y][v.hp] > b){
dp[v.x][v.y][v.hp] = b;
q.push(v);
}
} }
int ans = -;
for(i=; i< (<<); i++){
if(dp[ex][ey][i] != - && (dp[ex][ey][i]<ans || ans==-))
ans = dp[ex][ey][i];
}
printf("Case %d: %d\n",cas,ans);
}
return ;
}