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

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

解题思路总结

1. 输入读取：读取单词、网格的行数和列数，以及网格本身。
2. 方向定义：定义八个可能的搜索方向，涵盖所有直线方向。
3. 边界检查：确保坐标在网格范围内。
4. 直线匹配：对于每个起点，检查是否可以沿八个方向之一形成直线排列。
5. 直角匹配：对于每个起点，检查是否可以形成L形排列，确保两个方向垂直。
6. 计数：统计所有可能的匹配方式，并输出总次数。

代码优点

• 明确的方向定义：八个方向涵盖了所有可能的直线搜索方向。
• 高效的边界检查：确保搜索过程中不越界。
• 独立的匹配检查：直线和L形匹配的逻辑分离，代码结构清晰。
• 垂直方向判断：通过点积判断两个方向是否垂直，数学上简洁有效。

代码缺点

• 性能问题：对于较长的单词或较大的网格，递归搜索可能导致性能下降。
• 重复计算：某些情况下可能会重复检查相同的路径。
• 代码复杂度：涉及多个嵌套循环，可能影响可读性。

总结

该代码实现了对字母网格中单词的搜索，能够处理单词以直线或直角方式排列的情况。通过详细的注释和清晰的解题思路，代码易于理解和维护。