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

· · 题解

首先我们先把方法，思路，算法和优化考虑一下：

1.问题分析：信号在网格中传播，遇到行星（'/'或''）会偏转90度，遇到黑洞（'C'）或边界则停止。我们需要从四个方向（U, R, D, L）中选择一个，使得信号传播的时间最长。

2.关键观察：对于每个方向，模拟信号的传播路径。记录访问过的状态（位置和方向）以检测循环（无限循环）。如果遇到相同的状态（位置和方向）两次，则检测到循环。

3.算法选择：对每个方向进行深度优先搜索（DFS）或迭代模拟，使用记忆化来存储状态（行、列、方向）以避免重复计算和检测循环。

4.优化：由于网格大小最大为500x500，状态总数为4NM（约4500500=1e6），可以在每个方向上进行模拟，使用三维数组vis标记访问过的状态（行、列、方向）以检测循环。

实现细节：

定义方向映射：U(0), R(1), D(2), L(3)。

对于每个起始方向，模拟移动：根据当前方向移动，遇到行星时改变方向（根据行星类型）。

记录步数，如果进入循环则返回"Voyager"。

比较四个方向的步数，选择最大的（按优先级U、R、D、L）。

弄明白以上几点，接下来看一看我的AC代码：


#include<bits/stdc++.h>
using namespace std;
int a[4][2]={{-1,0},{0,1},{1,0},{0,-1}};// U, R, D, L
char b[4]={'U','R','D','L'};
string x[1005];
bool y[1005][1005][4];
bool cmp(int r,int c,int d,int& g,int n,int m){
    g=0;
    memset(y,false,sizeof(y));
    while(true){
        if(r<0||r>=n||c<0||c>=m) return false; // 离开网格
        if(x[r][c]=='C') return false; // 进入黑洞
        if(y[r][c][d]) return true; // 循环
        y[r][c][d]=true;
        g++;
        if(x[r][c]=='/') d=d^1;// 0<->1, 2<->3
        else if(x[r][c]=='\\') d = 3 - d; // 0<->3, 1<->2
        r += a[d][0];
        c += a[d][1];
    }
}
int main() {
    int n,m,ans,sum,s1=-1,s2=-1;
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>x[i];
    cin>>ans>>sum;
    ans--; 
    sum--; // 转换为0-indexed
    for(int i=0;i<4;i++){
        int g=0;
        bool k=cmp(ans,sum,i,g,n,m);
        if(k==1){
            cout<<b[i]<<endl<<"Voyager"<<endl;
            return 0;
        } 
        else{
            if(g>s1) {
                s1=g;
                s2=i;
            }
        }
    }
    cout<<b[s2]<<endl<<s1<<endl;
    return 0;
}