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

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

ai 2025/7/27 21:00:12

在CCC单词搜索游戏中，单词可以隐藏在字母网格中，以直线或直角的方式排列。以下是对代码的详细注释和解题思路的总结：

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

代码注释

#include <iostream>
#include <vector>
#include <string>using namespace std;// 定义八个可能的搜索方向
const int dx[8] = {-1,-1, 0, 1, 1, 1, 0,-1}; // 北、东北、东、东南、南、西南、西、西北
const int dy[8] = { 0, 1, 1, 1, 0,-1,-1,-1};int R, C; // 网格行数和列数
vector<string> grid; // 字母网格
string word; // 搜索区域分词
int word_len; // 单词长度// 检查坐标是否在网格范围内
bool inBounds(int x, int y) {return x >= 0 && x < R && y >= 0 && y < C;
}// 检查单词是否可以沿指定方向的直线排列
bool checkStraight(int x, int y, int dir) {for (int i = 0; i < word_len; ++i) {int nx = x + dx[dir] * i; // 计算下一个位置的行坐标int ny = y + dy[dir] * i; // 计算下一个位置的列坐标if (!inBounds(nx, ny) || grid[nx][ny] != word[i]) // 如果超出边界或字母不匹配return false; // 返回不匹配}return true; // 单词完全匹配
}// 检查单词是否可以以L形排列（直角）
bool checkLShape(int x, int y, int dir1, int dir2, int split) {// 检查第一段（从起点到分割点）for (int i = 0; i < split; ++i) {int nx = x + dx[dir1] * i;int ny = y + dy[dir1] * i;if (!inBounds(nx, ny) || grid[nx][ny] != word[i])return false;}// 从分割点开始，沿新的方向检查剩余部分int lx = x + dx[dir1] * (split - 1);int ly = y + dy[dir1] * (split - 1);for (int i = split; i < word_len; ++i) {lx += dx[dir2]; // 更新行坐标ly += dy[dir2]; // 更新列坐标if (!inBounds(lx, ly) || grid[lx][ly] != word[i])return false;}return true; // 单词完全匹配
}// 判断两个方向是否垂直
bool arePerpendicular(int dir1, int dir2) {return (dx[dir1] * dx[dir2] + dy[dir1] * dy[dir2]) == 0; // 点积为0则垂直
}int main() {cin >> word;word_len = word.length();cin >> R >> C;grid.resize(R);// 读取网格for (int i = 0; i < R; ++i) {grid[i] = "";for (int j = 0; j < C; ++j) {string ch;cin >> ch;grid[i] += ch;}}int count = 0;// 遍历每个单元格作为起点for (int x = 0; x < R; ++x) {for (int y = 0; y < C; ++y) {if (grid[x][y] != word[0]) continue; // 跳过不匹配首字母的单元格// 检查所有可能的直线排列for (int d = 0; d < 8; ++d) {if (checkStraight(x, y, d))count++;}// 检查所有可能的L形排列for (int d1 = 0; d1 < 8; ++d1) {for (int d2 = 0; d2 < 8; ++d2) {if (d1 == d2 || !arePerpendicular(d1, d2))continue; // 跳过相同方向或非垂直方向for (int split = 2; split < word_len; ++split) { // 分割点至少在第二个字母if (checkLShape(x, y, d1, d2, split))count++;}}}}}cout << count << endl; // 输出匹配次数return 0;
}