题解：P14814 [ICPC 2023 Yokohama R] Yokohama Phenomena

Fat__Cat · 2025-12-21 20:41:12 · 题解

这是一道比较简单的搜索板子题。

分析

我们需要求出格子四联通的前提下，有几个能走出 YOKOHAMA 的路径。

观察发现 n,m \leq 10 也就是说朴素的 深度优先搜索 即可解出本题。

需要注意的几点：

• 没有指定起点，须自己枚举，但是起点对应字符只能为 Y
• 可以重复经过一个格子，无需回溯

核心深搜代码如下：

const string tar="YOKOHAMA";
bool check(int i,int j,int p) //检测在第 p 步移至 a[i][j] 是否合法
{
    return i>=0&&j>=0&&i<n&&j<m&&a[i][j]==tar[p+1];
}
void dfs(int i,int j,int p) //p 代表这是已走的第 p 个字符
{
    if(p==7) //已经走完
    {
        res++;
        return;
    }
    //往可能的地方继续搜索
    if(check(i+1,j,p)) dfs(i+1,j,p+1);
    if(check(i,j+1,p)) dfs(i,j+1,p+1);
    if(check(i,j-1,p)) dfs(i,j-1,p+1);
    if(check(i-1,j,p)) dfs(i-1,j,p+1);
}

代码

~talk is cheap,show me the code.~

#include<bits/stdc++.h>
using namespace std;
int n,m,res;
char a[1000][1000];
const string tar="YOKOHAMA";
bool check(int i,int j,int p)
{
    return i>=0&&j>=0&&i<n&&j<m&&a[i][j]==tar[p+1];
}
void dfs(int i,int j,int p)
{
    if(p==7)
    {
        res++;
        return;
    }
    if(check(i+1,j,p)) dfs(i+1,j,p+1);
    if(check(i,j+1,p)) dfs(i,j+1,p+1);
    if(check(i,j-1,p)) dfs(i,j-1,p+1);
    if(check(i-1,j,p)) dfs(i-1,j,p+1);
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin>>a[i][j];
    for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(a[i][j]=='Y') dfs(i,j,0);
    cout<<res;
    return 0;
}

第三篇题解，请大家多多支持喵！