題目敘述：https://zerojudge.tw/ShowProblem?problemid=c145
解題想法：DFS + Backtracking
- 題目規定一律採蛇行路線，也就是往前一格，接下來就一定要左轉或右轉。也就是每次輪流沿 x 方向或 y 方向移動。
- 函數 dfs( ) 多用了一個參數 d，用來記錄移動方向(direction)。
- main( ) 呼叫兩次 dfs( )，一次先沿著 x 方向移動，另一次則沿著 y 方向移動，計算出最長的兜風路徑。
#include <iostream>
using namespace std;
int n, m, maxi, a[11][11];
void dfs(int x, int y, int d, int steps){
if (d == 0){
if ((x+1 < n && a[x+1][y]==0)|| (x-1 >= 0 && a[x-1][y]==0)){
if (x+1 < n && a[x+1][y]==0){
a[x+1][y] = 1;
dfs(x+1, y, 1, steps+1);
a[x+1][y] = 0;
}
if (x-1 >= 0 && a[x-1][y]==0){
a[x-1][y] = 1;
dfs(x-1, y, 1, steps+1);
a[x-1][y] = 0;
}
}else{
if (steps > maxi) maxi = steps;
}
}
else if (d == 1){
if ((y+1 < m && a[x][y+1]==0)|| (y-1 >= 0 && a[x][y-1]==0)){
if (y+1 < m && a[x][y+1]==0){
a[x][y+1] = 1;
dfs(x, y+1, 0, steps+1);
a[x][y+1] = 0;
}
if (y-1 >= 0 && a[x][y-1]==0){
a[x][y-1] = 1;
dfs(x, y-1, 0, steps+1);
a[x][y-1] = 0;
}
}else{
if (steps > maxi) maxi = steps;
}
}
}
int main(){
while (cin >> n >> m){
maxi = 0;
dfs(0, 0, 0, 1);
dfs(0, 0, 1, 1);
cout << maxi << "\n";
}
}