专栏文章

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

wwenqinghua1001
P13415题解参与者 3已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mioqzspe
此快照首次捕获于
2025/12/02 23:43
3 个月前
此快照最后确认于
2025/12/02 23:43
3 个月前
查看原文

前言

本题类似于 CSP-J 2024 T2。
题目传送门

思路

看到这题，首先想到的是暴力，没错！就是暴力。
暴力大家都会，但途中一定有两个问题。
第一个问题，就是如何判断信号是否可以在系统内无限循环。很好解决，只需判断在同一个点是否有一次以上向相同的方向发出信号。对于样例三，很明显，在第 1616 次遍历，信号在第 33 行第 33 列，出现了两次在同一个点向相同的方向发出信号，所以输出 Voyager。
第二个问题，输入的字符有 \，在编译的时候会报错。也好解决，在输入的时候把这个字符换成其它字符就行了。
首先，输入，我是将 \ 改成了 %。
CPP
	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;
接着进行递归，用 gg 数组来存储在同一个点是否有一次以上向相同的方向发出信号，记得清空。
CPP
	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);
然后输出，注意优先级，这就是主函数，opop 在 DFS 中解释。
CPP
	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;
最后，是最主要的遍历函数，用来暴力求出信号在系统中停留的最长时间，具体解释在代码中。
CPP
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 记录
CPP
#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;
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...