当前位置：首页 > web >正文

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

web 2025/7/27 20:38:05

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

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

解题思路

输入读取与初始化：
- 读取要搜索的单词和网格的行数、列数。
- 将网格存储为二维向量。
方向定义：
- 定义八个可能的搜索方向，包括上、右上、右、右下、下、左下、左、左上。
边界检查：
- 检查给定的坐标是否在网格范围内。
深度搜索：
- 从网格中每个与单词首字母匹配的位置开始，向八个方向进行深度搜索。
- 在搜索过程中，可以继续沿当前方向或在未转过弯的情况下沿垂直方向继续搜索。
计数：
- 统计所有可能的单词匹配方式，并输出总的匹配次数。

代码实现

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