**狀態定義**：(farmer, wolf, sheep, cabbage)，各 0/1 表示左右岸。合法狀態：農夫不在時，狼不吃羊、羊不吃菜。
**目標**：從 (0,0,0,0) 到 (1,1,1,1) 的最短路徑。
#include <bits/stdc++.h>
using namespace std;
struct State { uint8_t f, w, s, c; };
bool safe(const State& st) {
if (st.f != st.s && (st.w == st.s || st.s == st.c)) return false;
return true;
}
bool connected(const State& a, const State& b) {
int diff = (a.f!=b.f) + (a.w!=b.w) + (a.s!=b.s) + (a.c!=b.c);
return a.f != b.f && diff <= 2; // 農夫必動，最多帶一物
}
int encode(const State& st) { return (st.f<<3)|(st.w<<2)|(st.s<<1)|st.c; }
int main() {
vector<State> states;
for (int f=0;f<=1;++f) for(int w=0;w<=1;++w) for(int s=0;s<=1;++s) for(int c=0;c<=1;++c) {
State st{(uint8_t)f,(uint8_t)w,(uint8_t)s,(uint8_t)c};
if (safe(st)) states.push_back(st);
}
int N = states.size();
vector<vector<int>> adj(N);
for (int i=0;i// 迷宮以 0=路, 1=牆, 起點 (0,0), 終點 (n-1,m-1)
bool dfs(vector<string>& maze, int x, int y, vector<pair<int,int>>& path) {
int n=maze.size(), m=maze[0].size();
if(x<0||x>=n||y<0||y>=m||maze[x][y]!='0') return false;
path.emplace_back(x,y);
if(x==n-1 && y==m-1) return true;
maze[x][y]='2'; // 標記已訪問
static const int dx[4]={-1,1,0,0}, dy[4]={0,0,-1,1};
for(int d=0;d<4;++d) if(dfs(maze,x+dx[d],y+dy[d],path)) return true;
path.pop_back();
return false;
}
struct Triple { int row, col, val; };
struct SparseMatrix {
int rows, cols, terms;
vector<Triple> data; // 按行主序排序
SparseMatrix(int r, int c): rows(r), cols(c), terms(0) {}
void add(int r, int c, int v) {
if(v==0) return;
data.push_back({r,c,v});
++terms;
}
void sort() { sort(data.begin(), data.end(), [](auto&a,auto&b){ return a.row!=b.row?a.row| 題目 | 核心資料結構 | 核心演算法 | 關鍵細節 |
|---|---|---|---|
| 農夫過河 | 狀態編碼 (4-bit)、鄰接表 | BFS 最短路徑 | 合法狀態判定、農夫必動且最多帶一物 |
| 迷宮 | 二維字元陣列、路徑向量 | DFS 回溯 / BFS | 標記訪問避免循環、四方向擴展、邊界檢查 |
| 稀疏矩陣 | 三元組 (row,col,val) 陣列 | 歸併式加法 (雙指標) | 按行主序排序、同位置相加、結果為 0 時捨棄 |
建議： 先理解狀態空間建模（農夫過河）、圖搜尋模板（迷宮）、壓縮存儲與歸併（稀疏矩陣），再動手寫代碼。這三題涵蓋了資料結構課程 80% 的核心能力。
