HDU-5025 2014廣州網絡賽 Saving Tang Monk 狀壓+BFS
給出一個N*N的矩陣，開啟牢門需要收集齊m種鑰匙，且必須收集了前i-1種鑰匙才能收集第i種鑰匙，最終收集齊了回到關押唐僧的房間拯救唐僧，經過一個'S'的房間時需要額外耗時把蛇打死，蛇最多5條，所以狀壓一下用優先隊列BFS求最小時間即可。
#include
#include
#include
#include
#include
#include
#include
#define inf 1<<29
using namespace std;
const int maxn=111;
char str[maxn][maxn];
int n,m;
int ans;
int map[maxn][maxn];
int dp[maxn][maxn][11];//訪問到坐標(x,y)身上有i個鑰匙的步數
int dir[4][2]= {0,1,0,-1,1,0,-1,0};
struct node
{
int x,y;
int step;
int snake;
int k;
friend bool operator<(node a,node b)
{
return a.step>b.step;
}
};
int go(int x,int y)
{
if(x>=0&&x=0&&y q;
node front,now;
now.x=x;
now.y=y;
now.step=0;
now.snake=0;
now.k=0;
q.push(now);
while(!q.empty())
{
front=q.top();
q.pop();
x=front.x;
y=front.y;
if(str[x][y]=='T'&&front.k==m)
{
ans=min(ans,front.step);
}
for(int i=0;i<4;i++)
{
int fx=x+dir[i][0];
int fy=y+dir[i][1];
now.x=fx;
now.y=fy;
now.step=front.step+1;
now.snake=front.snake;
now.k=front.k;
if(go(fx,fy))
{
if(str[fx][fy]=='S')
{
int k=map[fx][fy];
if(((1<now.step&&now.step
