自动搬运

查看原文

来自洛谷，原作者为

	Lemonlwl **

搬运于2025-08-24 22:47:11，当前版本为作者最后更新于2023-06-08 12:33:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P9303 [CCC 2023 J5] CCC Word Hunt 题解

题意：

对于给定字符串 $W$，你需要在给定的矩阵中找到它。

分析：

查找方式一共有三种：

1. 水平或垂直查找。
2. 沿对角线查找。
3. 在以上查找过程中进行 $90$ 度翻折（只能翻折一次）查找。

思路：

本题是显而易见的深搜题，因此我们可以用三个函数分别进行三种查找方式的调用，则第三种查找我们可以在前两个查找过程中调用。

1. 函数 dfs1 为垂直或水平搜索，在每一个位置判断：若方向翻折 $90$ 度后的下一个字符与字符串的下一个字符相同则沿该方向翻折，使用 dfs3 继续搜索。

2. 函数 dfs2 为对角线搜索，在每一个位置判断：若方向翻折 $90$ 度后的下一个字符与字符串的下一个字符相同则沿该方向翻折，使用 dfs3 继续搜索。

3. 函数 dfs3 为翻折方向搜索，在每一个位置判断：若下一个字符与字符串的下一个字符相同则继续搜索。

注：在 $d$ 等于 $0$ 时，即第一个字符时不能翻折。

附上 AC 代码：

#include<iostream>
#include<cstring>
using namespace std;
string w;
int r,c,sum,len;
char a[105][105];
int x1[4]={-1,0,1,0};
int y1[4]={0,-1,0,1};
//水平与垂直方向。
int x2[4]={-1,1,1,-1};
int y2[4]={-1,-1,1,1};
//对角线方向。
void dfs3(int x,int y,int d,int dire,int flag){  //中途翻折方向，继续搜索。
	if(d==len-1){   //查到最后一个位置结束，下同。
		sum++;
		return;
	}
	if(flag==1){   //从水平或垂直方向翻折。
		int vx=x+x1[dire];
		int vy=y+y1[dire];
		//这里的dire是翻折过的方向，下同。
		if(vx>=1 && vy>=1 && vx<=r && vy<=c && a[vx][vy]==w[d+1]){
			dfs3(vx,vy,d+1,dire,1);
		}
	}
	if(flag==2){   //从对角线方向翻折。
		int vx=x+x2[dire];
		int vy=y+y2[dire];
		if(vx>=1 && vy>=1 && vx<=r && vy<=c && a[vx][vy]==w[d+1]){
			dfs3(vx,vy,d+1,dire,2);
		}
	}
}
void dfs1(int x,int y,int d,int dire){ //水平或垂直方向搜索。
	if(d==len-1){
		sum++;
		return;
	}
	int vx=x+x1[dire];
	int vy=y+y1[dire];
	if(vx>=1 && vy>=1 && vx<=r && vy<=c && a[vx][vy]==w[d+1]){
		dfs1(vx,vy,d+1,dire);
	}
	//翻折方向。
	int ax=x+x1[(dire+1)%4];
	int ay=y+y1[(dire+1)%4];
	//翻折向左。
	int bx=x+x1[(dire+3)%4];
	int by=y+y1[(dire+3)%4];
	//翻折向右。
	//中途翻折。
	if(d>0 && ax>=1 && ay>=1 && ax<=r && ay<=c && a[ax][ay]==w[d+1]){
		dfs3(ax,ay,d+1,(dire+1)%4,1);
	}
	if(d>0 && bx>=1 && by>=1 && bx<=r && by<=c && a[bx][by]==w[d+1]){
		dfs3(bx,by,d+1,(dire+3)%4,1);
	}
}
void dfs2(int x,int y,int d,int dire){ //对角线方向搜索。
	if(d==len-1){
		sum++;
		return;
	}
	int vx=x+x2[dire];
	int vy=y+y2[dire];
	if(vx>=1 && vy>=1 && vx<=r && vy<=c && a[vx][vy]==w[d+1]){
		dfs2(vx,vy,d+1,dire);
	}
	//翻折方向。
	int ax=x+x2[(dire+1)%4];
	int ay=y+y2[(dire+1)%4];
	//翻折向左。
	int bx=x+x2[(dire+3)%4];
	int by=y+y2[(dire+3)%4];
	//翻折向右。
	//中途翻折。
	if(d>0 && ax>=1 && ay>=1 && ax<=r && ay<=c && a[ax][ay]==w[d+1]){
		dfs3(ax,ay,d+1,(dire+1)%4,2);
	}
	if(d>0 && bx>=1 && by>=1 && bx<=r && by<=c && a[bx][by]==w[d+1]){
		dfs3(bx,by,d+1,(dire+3)%4,2);
	}
}
int main(){
	cin>>w>>r>>c;  //输入。
	len=w.length(); //长度。
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			cin>>a[i][j];  //输入。
		}
	}
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			if(a[i][j]==w[0]){
				//八个方向搜索。
				dfs1(i,j,0,0);
				dfs1(i,j,0,1);
				dfs1(i,j,0,2);
				dfs1(i,j,0,3);
				dfs2(i,j,0,0);
				dfs2(i,j,0,1);
				dfs2(i,j,0,2);
				dfs2(i,j,0,3);
			}
		}
	}
	cout<<sum<<endl; //输出。
	return 0;
}