HDU 3442 Three Kingdoms BFS + 優先隊列



已被周賽虐成掛零狗。
BFS + 優先隊列 == 最短路，貌似是可以這樣理解的。這樣得到的結果即為花費最少的一條路。貌似初級計劃裡面有一個類似的題。
因為受過的傷不會再受，所以需要抽象出第三維來表示受過的哪幾種傷（狀壓）。寒假集訓的時候還給大一的選手出過這種題。。。竟然還有臉給大一的講題。。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#pragma comment(linker, "/STACK:1024000000");
#define EPS (1e-6)
#define LL long long
#define ULL unsigned long long int
#define _LL __int64
#define _INF 0x3f3f3f3f
#define INF (1<<62)
#define Mod 1000000007

using namespace std;

char Map[51][51];

int hurt[51][51][5];

bool mark[51][51][33];

void Init_Hurt(int n,int m)
{
    int i,j,k,l;

    memset(hurt,0,sizeof(hurt));

    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(l = j-2;l <= j+2; ++l)
                    {
                        if(1 <= k && k <= n && 1 <= l && l <= m && abs(k-i)+ abs(l-j) <= 2)
                        {
                            hurt[k][l][0] = 1;
                        }
                    }
                }
            }
            else if(Map[i][j] == 'B')
            {
                for(k = i-3;k <= i+3; ++k)
                {
                    for(l = j-3;l <= j+3; ++l)
                    {
                        if(1 <= k && k <= n && 1 <= l && l <= m && abs(k-i)+ abs(l-j) <= 3)
                        {
                            hurt[k][l][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(l = j-2;l <= j+2; ++l)
                    {
                        if(1 <= k && k <= n && 1 <= l && l <= m && abs(k-i)+ abs(l-j) <= 2)
                        {
                            hurt[k][l][3] = 4;
                        }
                    }
                }
            }
            else if(Map[i][j] == 'E')
            {
                for(k = i-1;k <= i+1; ++k)
                {
                    for(l = j-1;l <= j+1; ++l)
                    {
                        if(1 <= k && k <= n && 1 <= l && l <= m && abs(k-i)+ abs(l-j) <= 1)
                        {
                            hurt[k][l][4] = 5;
                        }
                    }
                }
            }
        }
    }
}

struct N
{
    int x,y,sta,ans;
    bool operator < (const N &a) const
    {
        return a.ans < ans;
    }
};

int jx[] = {-1, 0, 1, 0};
int jy[] = { 0, 1, 0,-1};

bool Judge(char c)
{
    if(c == '$' || c == 'C' || c == '!' || c == '.')
        return true;
    return false;
}

void bfs(int n,int m,int s,int e)
{
    priority_queue q;

    N f,t;

    f.x = s,f.y = e,f.sta = 0,f.ans = 0;

    memset(mark,false,sizeof(mark));

    mark[s][e][0] = true;

    q.push(f);

    while(q.empty() == false)
    {
        f = q.top();
        q.pop();

        if(f.x != s || f.y != e)
        {
            for(int k = 0;k < 5; ++k)
            {
                if((f.sta&(1<