首页 > 代码库 > HDU 5040

HDU 5040

2024-07-23 23:25:27   217人阅读

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

题意比较难懂，有摄像头的位置是可以走的，每回合开始看做人先走摄像头再转，也就是说如果你这回合走之前没有摄像头在照你，走之后摄像头转过来被照，时间也只是+1，而不是+3（伪装是瞬间完成的）

解法显而易见，一个优先队列的bfs，vis数组多开一维，表示时间对4取模

#include <iostream>#include <cstring>#include <cstdio>#include <queue>#include <map>using namespace std ;int n ;int vis[505][505][4] ;int b[505][505][4] ;char mp[505][505] ;int aa,bb ;struct node{    int x,y ;    int step ;    friend bool operator <(node aaa,node bbb)    {        return aaa.step>bbb.step ;    }} ;int dx[]={-1,0,1,0,0} ;int dy[]={0,1,0,-1,0} ;int bfs(int x,int y){    memset(vis,0,sizeof(vis)) ;    priority_queue <node> q ;    node s ;    s.x=x ;s.y=y ;s.step=0 ;    vis[x][y][0]=1 ;    q.push(s) ;    while(!q.empty())    {        node u=q.top() ;        //printf("%d %d %d\n",u.x,u.y,u.step) ;        if(u.x==aa && u.y==bb)        {            return u.step ;        }        q.pop() ;        for(int i=0 ;i<5 ;i++)        {            int xx=u.x+dx[i] ;            int yy=u.y+dy[i] ;            if(xx<0 || xx>=n || yy<0 || yy>=n)continue ;            if(mp[xx][yy]==‘#‘)continue ;            node p ;            p=u ;            if(b[xx][yy][u.step%4] || b[u.x][u.y][u.step%4])            {                if(xx==u.x && yy==u.y && !vis[xx][yy][(u.step+1)%4])                {                    p.step++ ;                    vis[xx][yy][p.step%4]=1 ;                    q.push(p) ;                }                else if(!vis[xx][yy][(u.step+3)%4])                {                    p.x=xx ;p.y=yy ;                    p.step+=3 ;                    vis[xx][yy][p.step%4]=1 ;                    q.push(p) ;                }            }            else if(!vis[xx][yy][(u.step+1)%4])            {                p.x=xx ;p.y=yy ;p.step++ ;                vis[xx][yy][p.step%4]=1 ;                q.push(p) ;            }        }    }    return -1 ;}int main(){    int T ;    scanf("%d",&T) ;    for(int cas=1 ;cas<=T ;cas++)    {        scanf("%d",&n) ;        for(int i=0 ;i<n ;i++)            scanf("%s",mp[i]) ;        int x,y ;        memset(b,0,sizeof(b)) ;        for(int i=0 ;i<n ;i++)        {            for(int j=0 ;j<n ;j++)            {                if(mp[i][j]==‘M‘)                {                    x=i ;y=j ;                }                if(mp[i][j]==‘N‘)                {                    b[i][j][0]=b[i][j][1]=b[i][j][2]=b[i][j][3]=1 ;                    if(i-1>=0)b[i-1][j][0]=1 ;                    if(j+1<n)b[i][j+1][1]=1 ;                    if(j-1>=0)b[i][j-1][3]=1 ;                    if(i+1<n)b[i+1][j][2]=1 ;                }                if(mp[i][j]==‘W‘)                {                    b[i][j][0]=b[i][j][1]=b[i][j][2]=b[i][j][3]=1 ;                    if(i-1>=0)b[i-1][j][1]=1 ;                    if(j+1<n)b[i][j+1][2]=1 ;                    if(j-1>=0)b[i][j-1][0]=1 ;                    if(i+1<n)b[i+1][j][3]=1 ;                }                if(mp[i][j]==‘S‘)                {                    b[i][j][0]=b[i][j][1]=b[i][j][2]=b[i][j][3]=1 ;                    if(i-1>=0)b[i-1][j][2]=1 ;                    if(j+1<n)b[i][j+1][3]=1 ;                    if(j-1>=0)b[i][j-1][1]=1 ;                    if(i+1<n)b[i+1][j][0]=1 ;                }                if(mp[i][j]==‘E‘)                {                    b[i][j][0]=b[i][j][1]=b[i][j][2]=b[i][j][3]=1 ;                    if(i-1>=0)b[i-1][j][3]=1 ;                    if(j+1<n)b[i][j+1][0]=1 ;                    if(j-1>=0)b[i][j-1][2]=1 ;                    if(i+1<n)b[i+1][j][1]=1 ;                }                if(mp[i][j]==‘T‘)                {                    aa=i ;bb=j ;                }            }        }        printf("Case #%d: %d\n",cas,bfs(x,y)) ;    }    return 0 ;}
View Code

 

HDU 5040


联系
我们