prow2012-A3-0013

从 Trac 迁移的文章

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

原文章内容如下：

题意：一个地图里，小怪一直转圈侦查（4方向循环），问从(sx,sy)走到(dx,dy)最少被侦查到几次，同次数选择最少歩数。

spfa，f[x][y][d][0]表示走到(x,y),时间%4==d时，最少被侦查到的次数, f[x][y][d][1]表示歩数。

{{{

#include <iostream>
#include <vector>
#include <queue>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
using namespace std;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
int X[10000],Y[10000],D[10000],dir[10000];
char mat[200][200];
int f[200][200][4][2];
int Q[1000000][3];
bool mark[200][200][4];
int N,M,S;
int check(int x,int y,int t){
    int ans = 0;
    for (int i=0;i<S;i++)
        if (x==X[i]||y==Y[i]){
            int a = x-X[i],b = y-Y[i];
            int d = (dir[i]+t)%4;
            if (a==0) {
                if (dy[d]*b>0&&abs(b)<=D[i]) ans++;
            }else if (b==0){
                if (dx[d]*a>0&&abs(a)<=D[i]) ans++;
            }
        }
    return ans;
}

int main(){
    int i,j,x,y,a,b,L,R,xs,ys,xt,yt,oo=1000000000,_x,_y;
    int k,d,nd;
    while(scanf("%d%d%d",&N,&M,&S)!=EOF){
        for (i=1;i<=N;i++)
                scanf("%s",mat[i]+1);
        for (i=0;i<=N+1;i++){
            if (i==0||i==N+1)
                for (j=0;j<=M+1;j++)
                    mat[i][j] = '*';
            else mat[i][0]=mat[i][M+1] = '*';
        }
        for (i=0;i<S;i++){
            char ds[10];
            scanf("%d%d%d%s",&X[i],&Y[i],&D[i],ds);
            if (ds[0]=='N') dir[i] = 0;
            else if (ds[0] =='E') dir[i] = 1;
            else if (ds[0]=='S') dir[i] = 2;
            else dir[i] = 3;
            mat[X[i]][Y[i]] = '*';
        }
        scanf("%d%d%d%d",&xs,&ys,&xt,&yt);
        L = 0,R =1;
        Q[L][0] = xs,Q[L][1] = ys,Q[L][2] = 0;
        for (i=1;i<=N;i++)
            for (j=0;j<=M;j++)
                for (k=0;k<4;k++)
                f[i][j][k][0] = f[i][j][k][1] = oo,mark[i][j][k] = false;
        f[xs][ys][0][1] = 0;
        f[xs][ys][0][0] =check(xs,ys,0);

        mark[xs][ys][0] = true;
        while(L<R){
            x = Q[L][0],y = Q[L][1],d = Q[L][2];
            a = f[x][y][d][0],b = f[x][y][d][1];
    //  printf("%d %d %d :%d %d----\n",x,y,d,a,b);
            L++;
            mark[x][y][d] = false;
            for (i=0;i<4;i++){
                _x = x+dx[i];
                _y = y+dy[i];
                if (mat[_x][_y]!='*'){
                    a = f[x][y][d][0]+check(_x,_y,d+1);
                    b = f[x][y][d][1] +1;
                    nd = (d+1)%4;
                    if (a<f[_x][_y][nd][0]||(a==f[_x][_y][nd][0]&&b<f[_x][_y][nd][1])){
                        f[_x][_y][nd][0] = a;
                        f[_x][_y][nd][1] = b;
                        if (!mark[_x][_y][nd]){
                            mark[_x][_y][nd] = true;
                            Q[R][0] =_x;
                            Q[R][1] = _y;
                            Q[R][2] = nd;
                            R++;
                        }
                    }
                }
            }
        }
        int ans1 = oo,ans2 = oo;
        for (i=0;i<4;i++)
            if (f[xt][yt][i][0]<ans1||(f[xt][yt][i][0]==ans1&&f[xt][yt][i][1]<ans2)){
                ans1 = f[xt][yt][i][0];
                ans2 = f[xt][yt][i][1];
                }
        if (ans1==oo) printf("-1\n");
        else printf("%d %d\n",ans1,ans2);
    }
}

}}}

题意：一个地图里，小怪一直转圈侦查（4方向循环），问从(sx,sy)走到(dx,dy)最少被侦查到几次，同次数选择最少歩数。

spfa，f[x][y][d][0]表示走到(x,y),时间%4==d时，最少被侦查到的次数, f[x][y][d][1]表示歩数。

#include <iostream>
#include <vector>
#include <queue>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
using namespace std;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
int X[10000],Y[10000],D[10000],dir[10000];
char mat[200][200];
int f[200][200][4][2];
int Q[1000000][3];
bool mark[200][200][4];
int N,M,S;
int check(int x,int y,int t){
    int ans = 0;
    for (int i=0;i<S;i++)
        if (x==X[i]||y==Y[i]){
            int a = x-X[i],b = y-Y[i];
            int d = (dir[i]+t)%4;
            if (a==0) {
                if (dy[d]*b>0&&abs(b)<=D[i]) ans++;
            }else if (b==0){
                if (dx[d]*a>0&&abs(a)<=D[i]) ans++;
            }
        }
    return ans;
}
int main(){
    int i,j,x,y,a,b,L,R,xs,ys,xt,yt,oo=1000000000,_x,_y;
    int k,d,nd;
    while(scanf("%d%d%d",&N,&M,&S)!=EOF){
        for (i=1;i<=N;i++)
                scanf("%s",mat[i]+1);
        for (i=0;i<=N+1;i++){
            if (i==0||i==N+1)
                for (j=0;j<=M+1;j++)
                    mat[i][j] = '*';
            else mat[i][0]=mat[i][M+1] = '*';
        }
        for (i=0;i<S;i++){
            char ds[10];
            scanf("%d%d%d%s",&X[i],&Y[i],&D[i],ds);
            if (ds[0]=='N') dir[i] = 0;
            else if (ds[0] =='E') dir[i] = 1;
            else if (ds[0]=='S') dir[i] = 2;
            else dir[i] = 3;
            mat[X[i]][Y[i]] = '*';
        }
        scanf("%d%d%d%d",&xs,&ys,&xt,&yt);
        L = 0,R =1;
        Q[L][0] = xs,Q[L][1] = ys,Q[L][2] = 0;
        for (i=1;i<=N;i++)
            for (j=0;j<=M;j++)
                for (k=0;k<4;k++)
                f[i][j][k][0] = f[i][j][k][1] = oo,mark[i][j][k] = false;
        f[xs][ys][0][1] = 0;
        f[xs][ys][0][0] =check(xs,ys,0);
        mark[xs][ys][0] = true;
        while(L<R){
            x = Q[L][0],y = Q[L][1],d = Q[L][2];
            a = f[x][y][d][0],b = f[x][y][d][1];
    //  printf("%d %d %d :%d %d----\n",x,y,d,a,b);
            L++;
            mark[x][y][d] = false;
            for (i=0;i<4;i++){
                _x = x+dx[i];
                _y = y+dy[i];
                if (mat[_x][_y]!='*'){
                    a = f[x][y][d][0]+check(_x,_y,d+1);
                    b = f[x][y][d][1] +1;
                    nd = (d+1)%4;
                    if (a<f[_x][_y][nd][0]||(a==f[_x][_y][nd][0]&&b<f[_x][_y][nd][1])){
                        f[_x][_y][nd][0] = a;
                        f[_x][_y][nd][1] = b;
                        if (!mark[_x][_y][nd]){
                            mark[_x][_y][nd] = true;
                            Q[R][0] =_x;
                            Q[R][1] = _y;
                            Q[R][2] = nd;
                            R++;
                        }
                    }
                }
            }
        }
        int ans1 = oo,ans2 = oo;
        for (i=0;i<4;i++)
            if (f[xt][yt][i][0]<ans1||(f[xt][yt][i][0]==ans1&&f[xt][yt][i][1]<ans2)){
                ans1 = f[xt][yt][i][0];
                ans2 = f[xt][yt][i][1];
                }
        if (ans1==oo) printf("-1\n");
        else printf("%d %d\n",ans1,ans2);
    }
}