HDU 3345

http://acm.hdu.edu.cn/showproblem.php?pid=3345

最近重写usaco压力好大，每天写的都想吐。。

水一道bfs

注意的是开始旁边有敌人可以随便走，但是一旦开始走，再与敌人相邻行动力就变为0

#include <iostream>

#include <algorithm>

#include <string>

#include <stack>

#include <queue>

#include <cstdio>

#include <cstring>

using namespace std ;

char map[][] ;

char ans[][] ;

int vis[][] ;

int n,m,MV ;

typedef struct L{

    int x,y ;

    int mv ;

    friend bool operator <(L a,L b)

    {

        return a.mv<b.mv ;

    }

}L ;

L s ;

int dir[][]={,,,,,-,-,} ;

int ok(int x,int y)

{

    for(int i= ;i< ;i++)

    {

        int xx=x+dir[i][] ;

        int yy=y+dir[i][] ;

        if(xx< || yy< || xx>=n || yy>=m)continue ;

        if(map[xx][yy]=='E')

            return  ;

    }

    return  ;

}

void bfs()

{

    priority_queue <L> q ;

    L now,next ;

    memset(vis,,sizeof(vis)) ;

    q.push(s) ;

    vis[s.x][s.y]= ;

    while(!q.empty())

    {

        now=q.top() ;

        for(int i= ;i< ;i++)

        {

            int xx=now.x+dir[i][] ;

            int yy=now.y+dir[i][] ;

            if(xx< || yy< || xx>=n || yy>=m)continue ;

            if(vis[xx][yy])continue ;

            if(map[xx][yy]=='#')continue ;

            if(map[xx][yy]=='E')continue ;

            next.x=xx ;next.y=yy ;

            if(map[xx][yy]=='.' && now.mv>=)

            {

                next.mv=now.mv- ;

                if(ok(xx,yy))

                    next.mv= ;

                vis[xx][yy]= ;

                ans[xx][yy]='*' ;

                q.push(next) ;

            }

            if(map[xx][yy]=='T' && now.mv>=)

            {

                next.mv=now.mv- ;

                if(ok(xx,yy))

                    next.mv= ;

                vis[xx][yy]= ;

                ans[xx][yy]='*' ;

                q.push(next) ;

            }

            if(map[xx][yy]=='R' && now.mv>=)

            {

                next.mv=now.mv- ;

                if(ok(xx,yy))

                    next.mv= ;

                vis[xx][yy]= ;

                ans[xx][yy]='*' ;

                q.push(next) ;

            }

            if(map[xx][yy]=='P' && now.mv>=)

            {

                next.mv=now.mv- ;

                if(ok(xx,yy))

                    next.mv= ;

                vis[xx][yy]= ;

                q.push(next) ;

            }

        }

        q.pop() ;

    }

}

int main()

{

    int t ;

    scanf("%d",&t) ;

    while(t--)

    {

        scanf("%d%d%d",&n,&m,&MV) ;

        for(int i= ;i<n ;i++)

            scanf("%s",map[i]) ;

        for(int i= ;i<n ;i++)

        {

            for(int j= ;j<m ;j++)

            {

                ans[i][j]=map[i][j] ;

                if(map[i][j]=='Y')

                    s.x=i,s.y=j,s.mv=MV ;

            }

        }

        bfs() ;

        for(int i= ;i<n ;i++)

        {

            for(int j= ;j<m ;j++)

            {

                printf("%c",ans[i][j]) ;

            }

            putchar('\n') ;

        }

        putchar('\n') ;

    }

    return  ;

}