P9303 [CCC 2023 J5] CCC Word Hunt 题解

· · 题解

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;
}