Three Kingdoms（BFS＋优先队列）
2014-03-22 11:19:39         来源：Three Kingdoms（BFS＋优先队列）

https://acm.sdut.edu.cn:8080/vjudge/contest/view.action?cid=103#problem/J

A 攻击范围是 2,伤害值是 1

B 攻击范围是 3,伤害值是 2

C 凡是踏入这个点的都要受到 3 的伤害

D 攻击范围是 2,伤害值是 4

E 攻击范围是 1,伤害值是 5

\$ 代表刘备

! 代表终点

. 代表空地

# 代表墙

```#include
#include
#include
#include
#include
using namespace std;

char map[55][55];
int dir[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };

struct node
{
int x,y;
int hurt;
int sta;
bool operator < (const struct node &tmp)const
{
return hurt > tmp.hurt;
}
}p[2560];
int n,m;
int sx,sy,ex,ey;
int mark[55][55][33];
int hurt[55][55][6];

void init()
{
memset(hurt,0,sizeof(hurt));
int i,j,k,g;

for(i = 1; i <= n; i++)
{
for(j = 1; j <= m; j++)
{
if(map[i][j] == 'A')
{
for(k = i-2; k <= i+2; k++)
{
for(g = j-2; g <= j+2; g++)
{
if(k >= 1 && k <= n && g >= 1 && g <= m && abs(k-i)+abs(g-j) == 2)
hurt[k][g][0] = 1;
}
}
}

else if(map[i][j] == 'B')
{
for(k = i-3; k <= i+3; k++)
{
for(g = j-3; g <= j+3; g++)
{
if(k >= 1 && k <= n && g >= 1 && g <= m && abs(k-i)+abs(g-j) == 3)
hurt[k][g][1] = 2;
}
}
}

else if(map[i][j] == 'C')
{
hurt[i][j][2] = 3;
}

else if(map[i][j] == 'D')
{
for(k = i-2; k <= i+2; k++)
{
for(g = j-2; g <= j+2; g++)
{
if(k >= 1 && k <= n && g >= 1 && g <= m && abs(k-i)+abs(g-j) == 2)
hurt[k][g][3] = 4;
}
}
}

else if(map[i][j] == 'E')
{
for(k = i-1; k <= i+1; k++)
{
for(g = j-1; g <= j+1; g++)
{
if(k >= 1 && k <= n && g >= 1 && g <= m && abs(k-i)+abs(g-j) == 1)
hurt[k][g][4] = 5;
}
}
}
}
}
}

bool judge(int x, int y)
{
if(map[x][y] == 'C' || map[x][y] == '!' || map[x][y] == '.' || map[x][y] == '\$')
return true;
return false;
}

int bfs()
{
priority_queue  que;
while(!que.empty()) que.pop();
struct node tmp;
que.push( (struct node) {sx,sy,0,0} );
mark[sx][sy][0] = 1;

while(!que.empty())
{
struct node u = que.top();
que.pop();
if(u.x == ex && u.y == ey)
{
return u.hurt;
}

for(int d = 0; d <= 3; d++)
{
tmp.x = u.x + dir[d][0];
tmp.y = u.y + dir[d][1];
tmp.hurt = u.hurt;
tmp.sta = u.sta;
if(judge(tmp.x,tmp.y) && tmp.x >= 1 && tmp.x <= n && tmp.y >= 1 && tmp.y <= m)
{
for(int k = 0; k < 5; k++) //枚举五种塔，判断是否被该种塔攻击过
{
if( (tmp.sta & (1 << k)) == 0 && hurt[tmp.x][tmp.y][k])//若没被攻击过且在当前点时能够被周围的塔攻击
{
tmp.hurt += hurt[tmp.x][tmp.y][k];
tmp.sta += (1 << k); //标记已被攻击过
}
}

if( !mark[tmp.x][tmp.y][tmp.sta] )//没有访问过进队列
{
mark[tmp.x][tmp.y][tmp.sta] = 1;
que.push(tmp);
}
}
}
}
return -1;
}

int main()
{
int test;
scanf("%d",&test);

for(int item = 1; item <= test; item++)
{
scanf("%d %d",&n,&m);

for(int i = 1; i <= n; i++)
{
scanf("%s",map[i]+1);
for(int j = 1; j <= m; j++)
{
if(map[i][j] == '\$')
{
sx = i;
sy = j;
}
if(map[i][j] == '!')
{
ex = i;
ey = j;
}
}
}

init(); //预处理每一点的受到的攻击。
memset(mark,0,sizeof(mark));
int ans = bfs();
printf("Case %d: %d\n",item,ans);
}
return 0;
}
```