team2012-E1-mysol-0013

从 Trac 迁移的文章

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

原文章内容如下：

{{{
/* 解题报告 //

这题的题意就不详述了，总之是典型的格子题，用最短路来做

要注意的有几点：
1. 一个格子可能被多个守护者攻击到，所以要用 int 记录守护的人数
2. 在时刻 0，即玩家刚出现的那一刻，也会被攻击，所以不要漏了初值
3. 陷阱、守护者对于玩家而言都是不可通行的，但守护者可以用眼神攻击
   所以他们不会被这些东西阻拦，不需要去做额外的判断

// By 猛犸也钻地 @ 2012.07.21 */
}}}

{{{
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;

typedef pair<int,int> PII;
struct TPL{int t,r,c;};

const int INF = 1000000007;
const int mr[]={0,1,0,-1};
const int mc[]={1,0,-1,0};
const char* ms="ESWN";

char a[100][105];
PII dp[4][100][100];
int by[4][100][105];
int in[4][100][100];

int main(){
    int n,m,s;
    while(scanf("%d%d%d",&n,&m,&s)==3){
        memset(by,0,sizeof(by));
        for(int i=0;i<n;i++) scanf("%s",a[i]);
        for(int i=0;i<s;i++){
            int r,c,l;
            char s[5];
            scanf("%d%d%d%s",&r,&c,&l,s);
            a[--r][--c]='*',l++;
            for(int u=0;u<4;u++){
                int o=(strcspn(ms,s)+u)%4;
                for(int x=0;x<l;x++){
                    int dr=r+mr[o]*x;
                    int dc=c+mc[o]*x;
                    if(dr<0 || dc<0 || dr>=n || dc>=m) break;
                    by[u][dr][dc]++;
                }
            }
        }
        int sr,sc,tr,tc;
        scanf("%d%d%d%d",&sr,&sc,&tr,&tc);
        sr--,sc--,tr--,tc--;
        int e=by[0][sr][sc];
        queue<TPL> q;
        memset(dp,63,sizeof(dp));
        q.push((TPL){0,sr,sc});
        dp[0][sr][sc]=PII(e,0);
        while(q.size()){
            int t=q.front().t;
            int r=q.front().r;
            int c=q.front().c;
            PII w=dp[t][r][c];
            in[t][r][c]=false;
            q.pop();
            for(int o=0;o<4;o++){
                int dt=(t+1)%4;
                int dr=r+mr[o];
                int dc=c+mc[o];
                if(dr<0 || dc<0 || dr>=n || dc>=m || a[dr][dc]=='*') continue;
                PII cost(w.first+by[dt][dr][dc],w.second+1);
                if(cost<dp[dt][dr][dc]){
                    dp[dt][dr][dc]=cost;
                    if(!in[dt][dr][dc]){
                        in[dt][dr][dc]=true;
                        q.push((TPL){dt,dr,dc});
                    }
                }
            }
        }
        PII ans(INF,INF);
        for(int u=0;u<4;u++) ans=min(ans,dp[u][tr][tc]);
        if(ans.first!=INF) printf("%d %d\n",ans.first,ans.second);
        else puts("-1");
    }
}
}}}

/* 解题报告 //
这题的题意就不详述了，总之是典型的格子题，用最短路来做
要注意的有几点：
1. 一个格子可能被多个守护者攻击到，所以要用 int 记录守护的人数
2. 在时刻 0，即玩家刚出现的那一刻，也会被攻击，所以不要漏了初值
3. 陷阱、守护者对于玩家而言都是不可通行的，但守护者可以用眼神攻击
   所以他们不会被这些东西阻拦，不需要去做额外的判断
// By 猛犸也钻地 @ 2012.07.21 */

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
typedef pair<int,int> PII;
struct TPL{int t,r,c;};
const int INF = 1000000007;
const int mr[]={0,1,0,-1};
const int mc[]={1,0,-1,0};
const char* ms="ESWN";
char a[100][105];
PII dp[4][100][100];
int by[4][100][105];
int in[4][100][100];
int main(){
    int n,m,s;
    while(scanf("%d%d%d",&n,&m,&s)==3){
        memset(by,0,sizeof(by));
        for(int i=0;i<n;i++) scanf("%s",a[i]);
        for(int i=0;i<s;i++){
            int r,c,l;
            char s[5];
            scanf("%d%d%d%s",&r,&c,&l,s);
            a[--r][--c]='*',l++;
            for(int u=0;u<4;u++){
                int o=(strcspn(ms,s)+u)%4;
                for(int x=0;x<l;x++){
                    int dr=r+mr[o]*x;
                    int dc=c+mc[o]*x;
                    if(dr<0 || dc<0 || dr>=n || dc>=m) break;
                    by[u][dr][dc]++;
                }
            }
        }
        int sr,sc,tr,tc;
        scanf("%d%d%d%d",&sr,&sc,&tr,&tc);
        sr--,sc--,tr--,tc--;
        int e=by[0][sr][sc];
        queue<TPL> q;
        memset(dp,63,sizeof(dp));
        q.push((TPL){0,sr,sc});
        dp[0][sr][sc]=PII(e,0);
        while(q.size()){
            int t=q.front().t;
            int r=q.front().r;
            int c=q.front().c;
            PII w=dp[t][r][c];
            in[t][r][c]=false;
            q.pop();
            for(int o=0;o<4;o++){
                int dt=(t+1)%4;
                int dr=r+mr[o];
                int dc=c+mc[o];
                if(dr<0 || dc<0 || dr>=n || dc>=m || a[dr][dc]=='*') continue;
                PII cost(w.first+by[dt][dr][dc],w.second+1);
                if(cost<dp[dt][dr][dc]){
                    dp[dt][dr][dc]=cost;
                    if(!in[dt][dr][dc]){
                        in[dt][dr][dc]=true;
                        q.push((TPL){dt,dr,dc});
                    }
                }
            }
        }
        PII ans(INF,INF);
        for(int u=0;u<4;u++) ans=min(ans,dp[u][tr][tc]);
        if(ans.first!=INF) printf("%d %d\n",ans.first,ans.second);
        else puts("-1");
    }
}