题解：P13415 [COCI 2012/2013 #4] VOYAGER

· · 题解

前言

本题类似于 CSP-J 2024 T2。

题目传送门

思路

看到这题，首先想到的是暴力，没错！就是暴力。

暴力大家都会，但途中一定有两个问题。

第一个问题，就是如何判断信号是否可以在系统内无限循环。很好解决，只需判断在同一个点是否有一次以上向相同的方向发出信号。对于样例三，很明显，在第 16 次遍历，信号在第 3 行第 3 列，出现了两次在同一个点向相同的方向发出信号，所以输出 Voyager。

第二个问题，输入的字符有 \，在编译的时候会报错。也好解决，在输入的时候把这个字符换成其它字符就行了。

首先，输入，我是将 \ 改成了 %。

    cin>>n>>m;
    for(int i=1;i<=n;i++){
        string x;
        cin>>x;
        for(int j=1;j<=m;j++){
            a[i][j]=x[j-1];
            if(int(x[j-1])==92) // 92 = int('\')
                a[i][j]='%';
        }
    } 
    int x,y;
    cin>>x>>y;

接着进行递归，用 g 数组来存储在同一个点是否有一次以上向相同的方向发出信号，记得清空。

    memset(g,0,sizeof(g));
    int U=dfs(x,y,1);
    memset(g,0,sizeof(g));
    int R=dfs(x,y,2);
    memset(g,0,sizeof(g));
    int D=dfs(x,y,3);
    memset(g,0,sizeof(g));
    int L=dfs(x,y,4);

然后输出，注意优先级，这就是主函数，op 在 DFS 中解释。

    int ans=max(max(U,R),max(D,L));
    if(ans==U)
        cout<<"U";
    else if(ans==R)
        cout<<"R";
    else if(ans==D)
        cout<<"D";
    else
        cout<<"L";
    cout<<"\n";
    if(op==1)
        cout<<"Voyager";
    else
        cout<<ans;

最后，是最主要的遍历函数，用来暴力求出信号在系统中停留的最长时间，具体解释在代码中。

char a[505][505];
int g[505][505];
int n,m,op=0;
int dfs(int x,int y,int f){
    if(x<1||x>n||y<1||y>m||a[x][y]=='C'||op==1) // (1) 
        return 0;
    // 超出边界，遇到黑洞，无限循环
    // 返回 0，退出 dfs 
    if(a[x][y]=='/'){
        if(f==1) f=2;
        else if(f==2) f=1;
        else if(f==3) f=4;
        else if(f==4) f=3;
    }
    // 反弹情况 1 
    if(a[x][y]=='%'){
        // % 替换 \
        // 不然会报错 
        if(f==1) f=4;
        else if(f==2) f=3;
        else if(f==3) f=2;
        else if(f==4) f=1;
    }
    // 反弹情况 2
    if(g[x][y]==f){
        op=1;
        return 0;
        // 有环，op 标记一下，作为最优答案。
        // 后面不用判断了，(1)处的 op==1 特判就是此作用。 
    }
    g[x][y]=f;
    // 标记，用于判断循环 
    if(f==1) return dfs(x-1,y,f)+1;
    if(f==2) return dfs(x,y+1,f)+1;
    if(f==3) return dfs(x+1,y,f)+1;
    if(f==4) return dfs(x,y-1,f)+1;
    // 四个方向 
}

代码

AC 记录

#include<bits/stdc++.h>
using namespace std;
char a[505][505];
int g[505][505];
int n,m,op=0;
int dfs(int x,int y,int f){
    if(x<1||x>n||y<1||y>m||a[x][y]=='C'||op==1)
        return 0;
    if(a[x][y]=='/'){
        if(f==1) f=2;
        else if(f==2) f=1;
        else if(f==3) f=4;
        else if(f==4) f=3;
    }
    if(a[x][y]=='%'){
        if(f==1) f=4;
        else if(f==2) f=3;
        else if(f==3) f=2;
        else if(f==4) f=1;
    }
    if(g[x][y]==f){
        op=1;
        return 0;
    }
    g[x][y]=f;
    if(f==1) return dfs(x-1,y,f)+1;
    if(f==2) return dfs(x,y+1,f)+1;
    if(f==3) return dfs(x+1,y,f)+1;
    if(f==4) return dfs(x,y-1,f)+1;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        string x;
        cin>>x;
        for(int j=1;j<=m;j++){
            a[i][j]=x[j-1];
            if(int(x[j-1])==92)
                a[i][j]='%';
        }
    } 
    int x,y;
    cin>>x>>y;
    memset(g,0,sizeof(g));
    int U=dfs(x,y,1);
    memset(g,0,sizeof(g));
    int R=dfs(x,y,2);
    memset(g,0,sizeof(g));
    int D=dfs(x,y,3);
    memset(g,0,sizeof(g));
    int L=dfs(x,y,4);
    int ans=max(max(U,R),max(D,L));
    if(ans==U)
        cout<<"U";
    else if(ans==R)
        cout<<"R";
    else if(ans==D)
        cout<<"D";
    else
        cout<<"L";
    cout<<"\n";
    if(op==1)
        cout<<"Voyager";
    else
        cout<<ans;
    return 0;
}