在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;
}
總結
以上代碼實現了對字母網格中單詞的搜索，能夠處理單詞以直線或直角方式排列的情況。通過深度搜索，代碼能夠有效地找出所有可能的匹配，并統計匹配次數。
