2012-A3-0013

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

题意:一个N×M的格子地图，单位时间可以走一格，有些格不可以走，有些格有每过一个单位时间转向的NPC，在改时刻经过他面向的一定距离的格子会发生一次事件，

指定起点和终点，求一条路径最少发生几次事件，以及此状况下的最短路径长度..

需要注意的几点和背景游戏中不一样的设定，NPC面向的距离不因不可通行的格子而减少，每个NPC不会只触发一次事件（可以触发多次）.

所有面向方向以模4为循环，可记录每个地点在模4时间下的触发事件数，然后记忆化BFS，记忆每个地点模4时间下的最小代价,最小代价是双关键字的。

{{{
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
#define go(i,n) for(size_t i=0;i<n;++i)
#define F first
#define S second
const char*d="ESWN";
const int mx[4]={0,1,0,-1},my[4]={1,0,-1,0};
typedef pair<int,int> ii;
const ii operator+(const ii&a,int b){return ii(a.F+b,a.S+1);}
char s[104][128];
ii f[104][104][4];
int p[104][104][4];
int main(){
for(int sx,sy,dx,dy,n,m,w;~scanf("%d%d%d ",&n,&m,&w);){
    go(i,n)gets(s[i+1]+1);
    go(i,n)go(j,m)memset(f[i+1][j+1],0x1f,32),memset(p[i+1][j+1],0,16);
    go(i,w){int x,y,l,k;
        scanf("%d%d%d ",&x,&y,&l);
        s[x][y]='*';k=strchr(d,getchar())-d;
        go(j,4){int a=x,b=y;
            go(_,l){a+=mx[k],b+=my[k];
                if(!a||!b||a>n||b>m)break;
                ++p[a][b][j];
            }(++k)&=3;
        }
    }
    scanf("%d%d%d%d",&sx,&sy,&dx,&dy);
    queue<int> q;
    f[sx][sy][0]=ii(p[sx][sy][0],0);
    q.push(sx<<16|sy<<2);
    for(int k,a,b;q.size();q.pop()){
        sx=q.front()>>16;
        sy=q.front()>>2&127;
        k=q.front()&3;
        go(j,4){
            a=sx+mx[j];
            b=sy+my[j];
            if(!a||!b||a>n||b>m||s[a][b]=='*')continue;
            ii t =f[sx][sy][k]+p[a][b][k+1&3];
            if(t<f[a][b][k+1&3])
                f[a][b][k+1&3]=t,q.push(a<<16|b<<2|(k+1&3));
        }
    }
    ii t =min(min(f[dx][dy][0],f[dx][dy][1]),min(f[dx][dy][2],f[dx][dy][3]));
    (t.F&0x10000000)?puts("-1"):printf("%d %d\n",t.F,t.S);
}
}
}}}

题意:一个N×M的格子地图，单位时间可以走一格，有些格不可以走，有些格有每过一个单位时间转向的NPC，在改时刻经过他面向的一定距离的格子会发生一次事件，

指定起点和终点，求一条路径最少发生几次事件，以及此状况下的最短路径长度..

需要注意的几点和背景游戏中不一样的设定，NPC面向的距离不因不可通行的格子而减少，每个NPC不会只触发一次事件（可以触发多次）.

所有面向方向以模4为循环，可记录每个地点在模4时间下的触发事件数，然后记忆化BFS，记忆每个地点模4时间下的最小代价,最小代价是双关键字的。

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
#define go(i,n) for(size_t i=0;i<n;++i)
#define F first
#define S second
const char*d="ESWN";
const int mx[4]={0,1,0,-1},my[4]={1,0,-1,0};
typedef pair<int,int> ii;
const ii operator+(const ii&a,int b){return ii(a.F+b,a.S+1);}
char s[104][128];
ii f[104][104][4];
int p[104][104][4];
int main(){
for(int sx,sy,dx,dy,n,m,w;~scanf("%d%d%d ",&n,&m,&w);){
    go(i,n)gets(s[i+1]+1);
    go(i,n)go(j,m)memset(f[i+1][j+1],0x1f,32),memset(p[i+1][j+1],0,16);
    go(i,w){int x,y,l,k;
        scanf("%d%d%d ",&x,&y,&l);
        s[x][y]='*';k=strchr(d,getchar())-d;
        go(j,4){int a=x,b=y;
            go(_,l){a+=mx[k],b+=my[k];
                if(!a||!b||a>n||b>m)break;
                ++p[a][b][j];
            }(++k)&=3;
        }
    }
    scanf("%d%d%d%d",&sx,&sy,&dx,&dy);
    queue<int> q;
    f[sx][sy][0]=ii(p[sx][sy][0],0);
    q.push(sx<<16|sy<<2);
    for(int k,a,b;q.size();q.pop()){
        sx=q.front()>>16;
        sy=q.front()>>2&127;
        k=q.front()&3;
        go(j,4){
            a=sx+mx[j];
            b=sy+my[j];
            if(!a||!b||a>n||b>m||s[a][b]=='*')continue;
            ii t =f[sx][sy][k]+p[a][b][k+1&3];
            if(t<f[a][b][k+1&3])
                f[a][b][k+1&3]=t,q.push(a<<16|b<<2|(k+1&3));
        }
    }
    ii t =min(min(f[dx][dy][0],f[dx][dy][1]),min(f[dx][dy][2],f[dx][dy][3]));
    (t.F&0x10000000)?puts("-1"):printf("%d %d\n",t.F,t.S);
}
}