P9303 [CCC 2023 J5] CCC Word Hunt

ccg12345 · 2023-05-21 19:23:50 · 题解

思路

看到题目后我立马想到了搜索方法中的洪水填充。

首先输入后先遍历一遍所有的字符，看与字符串的第一个字符是否相同，若相同则可以以这个点为起点开始搜索。每次若出格或不与想要的字符相同则立马返回，若字符一一对应则让结果加一。

因为可以在中途转 90 度，所以我们 8 个方向均要搜索，但要注意转弯时需要不是第一个字符且还未转过弯。

附代码：

#include <bits/stdc++.h>
using namespace std;
int dx[8] = {0, -1, -1, -1, 0, 1, 1, 1}, dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, r, c, ans = 0;
//dx[8],dy[8]分别是向8个方向分别移动后的行列变化，ans是总数
char a[105][105];
string s;
void srh(int x, int y, int now, int t, bool k)//分别是横坐标，纵坐标，进行到字符串的第几个字符，搜索方向和当前是否转过弯
{
    if(x <= 0 || x > r || y <= 0 || y > c || a[x][y] != s[now])
        return ;//字符出格或与s中的字符不匹配时退出
    if(now == s.length() - 1) 
    {
        ans++;
        return ;
    }//与字符串匹配，答案数加一
    srh(x + dx[t], y + dy[t], now + 1, t, k);
    if(k && now != 0)
    {
        srh(x, y, now, (t + 6) % 8, false);
        srh(x, y, now, (t + 2) % 8, false);
    }//若拐弯了立即将k设为false
}
int main()
{
    cin >> s;
    cin >> r >> c;
    for(register int i = 1; i <= r; i++)
        for(register int j = 1; j <= c; j++)
            cin >> a[i][j];
    for(register int i = 1; i <= r; i++)
        for(register int j = 1; j <= c; j++)
            if(a[i][j] == s[0])
                for(register int k = 0; k < 8; k++)
                    srh(i, j, 0, k, true);//若与字符串第零个字符相同，则从此点开始搜索
    cout << ans << endl;
    return 0;
}