2005 年 Google 中國程式設計挑戰賽入圍賽的一道 Hard/Mid 級題目 WordPath。給定字母矩陣 grid 與目標單字 find，從任意起點出發，可向 8 方向（含對角線）移動，格子可重複使用但不可連續停留同一格。求符合條件的路徑總數，超過 1,000,000,000 回傳 -1。
| Grid | Find | 輸出 | 說明 |
|---|---|---|---|
| {"ABC","FED","GHI"} | "ABCDEFGHI" | 1 | 唯一路徑，每格用一次 |
| {"ABC","FED","GAI"} | "ABCDEA" | 2 | E→A 有兩種走法 |
| {"AA","AA"} | "AAAA" | 108 | 4起點 × 3³ 方向選擇 |
| 5×5 全 "A" | 11 個 "A" | -1 | 路徑數超過 10 億 |
| {"AB","CD"} | "AA" | 0 | 不可連續停留同格 |
struct POS { int x, y, count; };
typedef vector VETPOS;
int findStrLen = find.length();
int gridSize = grid.size();
int gridStrLen = grid[0].length();
vector vec(findStrLen); // vec[k] 存放 find[k] 在 grid 的所有座標
for (int i = 0; i < gridSize; i++)
for (int j = 0; j < gridStrLen; j++)
for (int k = 0; k < findStrLen; k++)
if (find[k] == grid[i][j]) {
POS ps = {j, i, 1}; // 起始位置 count=1
vec[k].push_back(ps);
}
vec[i][j].count 表示「走到 find[i] 這個字元、且位於 grid 某座標」的路徑數。
vec[0][*].count = 1（每個起點 1 條路徑）cur.count = Σ pre[k].count，其中 pre[k] 為上一字元所有可移動到達 cur 位置的座標max(|x1-x2|, |y1-y2|) == 1 且不全為 0pathCountint pathCount(POS& ps, VETPOS& pre) {
ps.count = 0;
for (int i = 0; i < pre.size(); i++) {
int xAbs = abs(ps.x - pre[i].x);
int yAbs = abs(ps.y - pre[i].y);
if ((xAbs == 1 && yAbs < 2) || (yAbs == 1 && xAbs < 2)) {
ps.count += pre[i].count; // 累加可達路徑數
}
}
return ps.count;
}
VETPOS midVes;
for (int i = 1; i < findStrLen; i++) {
midVes.clear();
for (int j = 0; j < vec[i].size(); j++) {
POS cur = vec[i][j];
if (pathCount(cur, vec[i-1])) // 有可達路徑
midVes.push_back(cur);
}
vec[i].clear();
if (midVes.empty()) return 0; // 斷路
vec[i] = midVes; // 只保留有效位置
}
// 統計終點總路徑數
int total = 0;
for (int j = 0; j < vec[findStrLen-1].size(); j++) {
total += vec[findStrLen-1][j].count;
if (total > 1000000000) return -1;
}
return total;
class WordPath {
struct POS { int x, y, count; };
typedef vector VETPOS;
public:
int countPaths(vector grid, string find) {
// ... 完整實作見上方邏輯 ...
}
private:
int pathCount(POS& ps, VETPOS& pre) { /* ... */ }
};
j < grid[i].length() 即可相容歡迎大家提出更優解法或指正錯誤！聯繫：txqc4@sohu.com
