NYOJ 284 탱크 대전

제목 링크:http://acm.nyist.net/JudgeOnline/problem.php?pid=284
BFS 는 최 단 로 를 구 했다. 이 문 제 는 'B' 점 에 가 려 면 2 시간 이 걸 리 고 'E' 는 1 시간 이 걸 리 기 때문에 하나의 우선 대기 열 을 사용 해 야 한다. 우선 순 위 는 작은 선 출 팀 이 고 나머지 는 템 플 릿 이다.
코드:

#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

#define inf 0x3f3f3f3f
int stx,sty;
int enx,eny;
int n,m;
int v[305][305];

typedef struct p
{
    int x,y;
    int step;
} Node;
struct cmp
{
    bool operator()(const Node a,const Node b)
    {
        return a.step > b.step;
    }
};
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};
char s[305][305];
priority_queue<Node,vector<Node>,cmp> pq;
int flag;
int bfs()

{
    memset(v,0,sizeof v);
    Node start;
    start.x = stx;
    start.y = sty;
    start.step = 0;
    pq.push(start);
    while(!pq.empty())
    {
        Node head = pq.top();
        pq.pop();
        for(int i = 0; i < 4; ++i)
        {
            Node t;
            t.x = head.x + dx[i];
            t.y = head.y + dy[i];
            if(t.x == enx && t.y == eny)
            {
                return head.step + 1;
            }
            if(t.x < 0 || t.x > n - 1 || t.y < 0 || t.y > m - 1 ||s[t.x][t.y] == 'R'|| s[t.x][t.y] == 'S')
                continue;
            if(!v[t.x][t.y])
            {
                if(s[t.x][t.y] == 'B')
                    t.step = head.step + 2;
                else if(s[t.x][t.y] == 'E')
                    t.step = head.step + 1;
                pq.push(t);
                v[t.x][t.y] = 1;
            }
        }
    }
    return -1;
}
void clear()

{
    while(!pq.empty())
        pq.pop();
}
int main()

{
    while(~scanf("%d%d",&n,&m),m + n)
    {
        for(int i = 0; i < n; ++i)
        {
            scanf("%s",s[i]);
            for(int j = 0; j < m; ++j)
                if(s[i][j] == 'Y')
                {
                    stx = i;
                    sty = j;
                }
                else if(s[i][j] == 'T')
                {
                    enx = i;
                    eny = j;
                }
        }
        //printf("%d %d %d %d
",stx,sty,enx,eny);
        printf("%d
",bfs());
        clear(); //       ，  WA
    }
    return 0;
}