Three Kingdoms（BFS＋優先隊列）

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

題意：

給一張 n*m 的地圖，上面有一些帶有攻擊性的塔

A 攻擊范圍是 2,傷害值是 1

B 攻擊范圍是 3,傷害值是 2

C 凡是踏入這個點的都要受到 3 的傷害

D 攻擊范圍是 2,傷害值是 4

E 攻擊范圍是 1,傷害值是 5

$ 代表劉備

! 代表終點

. 代表空地

# 代表牆

劉備不能走到 A,B,D,E ,但是可以走到 . 和 C

劉備不會被同樣的塔傷害兩次.

問到達目的地需要的最少HP

思路：開始定義每個節點增加一個vis[]，標記到達該點時已經被哪些塔傷害過。但是BFS是一個動態的搜索，搜索到這個點時就會把原來的vis[]覆蓋掉，200+行的代碼。。。

正確的思路應該是對訪問數組增加一維，mark[n][m][32],可以想象成對每個點多增加了一個限制，即該點受到塔傷害的情況。共有ABCDE五種塔，那麼共有32中傷害情況。當BFS到某一點時，先根據前一個點判斷它是否受到某種塔的攻擊，如果沒受到過，那麼就會被攻擊並標記在這以狀態時已經被攻擊。

#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;
}