hdu 3345 War Chess （bfs+優先隊列）

War Chess

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1732 Accepted Submission(s): 416


Problem Description War chess is hh's favorite game:
In this game, there is an N * M battle map, and every player has his own Moving Val (MV). In each round, every player can move in four directions as long as he has enough MV. To simplify the problem, you are given your position and asked to output which grids you can arrive.

In the map:
"Y' is your current position (there is one and only one Y in the given map).
'.' is a normal grid. It costs you 1 MV to enter in this gird.
'T' is a tree. It costs you 2 MV to enter in this gird.
'R' is a river. It costs you 3 MV to enter in this gird.
'#' is an obstacle. You can never enter in this gird.
'E's are your enemies. You cannot move across your enemy, because once you enter the grids which are adjacent with 'E', you will lose all your MV. Here “adjacent” means two grids share a common edge.
'P's are your partners. You can move across your partner, but you cannot stay in the same grid with him final, because there can only be one person in one grid.You can assume the Ps must stand on '.' . so ,it also costs you 1 MV to enter this grid.
Input The first line of the inputs is T, which stands for the number of test cases you need to solve.
Then T cases follow:
Each test case starts with a line contains three numbers N,M and MV (2<= N , M <=100,0<=MV<= 65536) which indicate the size of the map and Y's MV.Then a N*M two-dimensional array follows, which describe the whole map.
Output Output the N*M map, using '*'s to replace all the grids 'Y' can arrive (except the 'Y' grid itself). Output a blank line after each case.
Sample Input

5
3 3 100
...
.E.
..Y

5 6 4
......
....PR
..E.PY
...ETT
....TT

2 2 100
.E
EY

5 5 2
.....
..P..
.PYP.
..P..
.....

3 3 1
.E.
EYE
...

Sample Output

...
.E*
.*Y

...***
..**P*
..E*PY
...E**
....T*

.E
EY

..*..
.*P*.
*PYP*
.*P*.
..*..

.E.
EYE
.*.

Author shǎ崽

bfs+優先隊列，剛開始沒有優化，果斷超時，第二次竟然因為優先級符號TLE！！（該記得的東西真得記牢）

使用mark數組記錄該點MV值大小，初始化為零，搜索時只有當從某個點到達當前點使MV變大時才把該點值更新；入隊時判斷該點MV值是否大於零，大於則入隊。

具體看代碼：

#include"stdio.h"
#include"string.h"
#include"queue"
#include"vector"
#include"algorithm"
using namespace std;
#define N 105
#define max(a,b) (a>b?a:b)
int mark[N][N],n,m,v;
int dir[4][2]={0,1,0,-1,-1,0,1,0};
char str[N][N];
struct node
{
    int x,y,d;
    friend bool operator<(node a,node b)
    {
        return a.d=0&&x=0&&yq;
    node cur,next;
    cur.x=x;cur.y=y;cur.d=v;
    q.push(cur);
    memset(mark,-1,sizeof(mark));
    mark[x][y]=v; 
    while(!q.empty())
    {
        cur=q.top();
        q.pop();
        for(i=0;i<4;i++)
        {
            next.x=x=dir[i][0]+cur.x;
            next.y=y=dir[i][1]+cur.y;
            if(judge(x,y))
            {
                if(str[x][y]=='.'||str[x][y]=='P')
                    t=cur.d-1;
                else if(str[x][y]=='T')
                    t=cur.d-2;
                else if(str[x][y]=='R')
                    t=cur.d-3;
                else
                    t=-1;
                if(ok(x,y)&&t>0)
                    t=0;        //戰斗力減為0
                if(t>0&&t>mark[x][y])
                {
                    next.d=t;
                    q.push(next);
                }
                mark[x][y]=max(mark[x][y],t);
            }
        }
    }
}
int main()
{
    int T,i,j;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&n,&m,&v);
        for(i=0;i=0)
                {
                    if(str[i][j]!='P'&&str[i][j]!='Y')
                        printf("*");
                    else
                        printf("%c",str[i][j]);
                }
                else
                    printf("%c",str[i][j]);
            }
            puts("");
        }
        puts("");
    }
    return 0;
}