【洛谷P9303题解】AC- [CCC 2023 J5] CCC Word Hunt

在CCC单词搜索游戏中，单词隐藏在一个字母网格中。目标是确定给定单词在网格中隐藏的次数。单词可以以直线或直角的方式排列。以下是详细的解题思路及代码实现：

传送门： https://www.luogu.com.cn/problem/P9303

解题思路

1. 输入读取与初始化：

   • 读取要搜索的单词和网格的行数、列数。
   • 将网格存储为二维向量。

2. 方向定义：

   • 定义八个可能的搜索方向，包括上、右上、右、右下、下、左下、左、左上。

3. 边界检查：

   • 检查给定的坐标是否在网格范围内。

4. 深度搜索：

   • 从网格中每个与单词首字母匹配的位置开始，向八个方向进行深度搜索。
   • 在搜索过程中，可以继续沿当前方向或在未转过弯的情况下沿垂直方向继续搜索。

5. 计数：

   • 统计所有可能的单词匹配方式，并输出总的匹配次数。

代码实现

#include <iostream>
#include <vector>
#include <string>using namespace std;int r, c;
string word;
int length;
vector<vector<string>> graph;// 定义八个可能的搜索方向
const int dx[8] = {-1,-1, 0, 1, 1, 1, 0,-1};
const int dy[8] = { 0, 1, 1, 1, 0,-1,-1,-1};// 检查坐标是否在网格范围内
bool good(int x, int y) {return x >= 0 && x < r && y >= 0 && y < c;
}// 深度搜索函数
int search(int x, int y, int cur, bool turned, int dirn) {if (cur == length - 1) return 1; // 找到完整匹配int cnt = 0;// 继续沿当前方向搜索int nx = x + dx[dirn], ny = y + dy[dirn];if (good(nx, ny) && graph[nx][ny] == string(1, word[cur + 1])) {cnt += search(nx, ny, cur + 1, turned, dirn);}// 如果未转过弯，尝试沿垂直方向搜索if (!turned) {int turnDirs[2] = {(dirn + 2) % 8, (dirn + 6) % 8}; // 计算垂直方向for (int k = 0; k < 2; ++k) {int newDir = turnDirs[k];int tx = x + dx[newDir], ty = y + dy[newDir];if (good(tx, ty) && graph[tx][ty] == string(1, word[cur + 1])) {cnt += search(tx, ty, cur + 1, true, newDir);}}}return cnt;
}int main() {cin >> word;length = word.length();cin >> r >> c;// 初始化网格graph.resize(r, vector<string>(c));for (int i = 0; i < r; ++i)for (int j = 0; j < c; ++j)cin >> graph[i][j];int count = 0;// 遍历网格，寻找所有可能的起点for (int i = 0; i < r; ++i) {for (int j = 0; j < c; ++j) {if (graph[i][j] == string(1, word[0])) { // 找到单词首字母for (int k = 0; k < 8; ++k) { // 尝试所有方向int ni = i + dx[k], nj = j + dy[k];if (good(ni, nj) && graph[ni][nj] == string(1, word[1])) { // 确保第二字母匹配count += search(ni, nj, 1, false, k); // 开始深度搜索}}}}}cout << count << endl; // 输出结果return 0;
}

总结

以上代码实现了对字母网格中单词的搜索，能够处理单词以直线或直角方式排列的情况。通过深度搜索，代码能够有效地找出所有可能的匹配，并统计匹配次数。