題目敘述:https://zerojudge.tw/ShowProblem?problemid=c780
解題想法:DFS + Backtracking
#include <iostream>
using namespace std;
int n, m, maxi, a[9][9];
void func(int x, int y, int steps){
int count = 0;
bool flag = false;
for (int i = x+1; i < n; i++){
if (a[i][y] == 1) count++;
if (count == 2){
a[i][y] = 0;
func(i, y, steps+1);
a[i][y] = 1;
break;
}
}
if (count >= 2) flag = true;
count = 0;
for (int i = x-1; i >= 0; i--){
if (a[i][y] == 1) count++;
if (count == 2){
a[i][y] = 0;
func(i, y, steps+1);
a[i][y] = 1;
break;
}
}
if (count >= 2) flag = true;
count = 0;
for (int i = y+1; i < m; i++){
if (a[x][i] == 1) count++;
if (count == 2){
a[x][i] = 0;
func(x, i, steps+1);
a[x][i] = 1;
break;
}
}
if (count >= 2) flag = true;
count = 0;
for (int i = y-1; i >= 0; i--){
if (a[x][i] == 1) count++;
if (count == 2){
a[x][i] = 0;
func(x, i, steps+1);
a[x][i] = 1;
break;
}
}
if (count >= 2) flag = true;
if (!flag && steps > maxi) maxi = steps;
}
int main(){
while (cin >> n >> m){
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
a[i][j] = 1;
}
}
a[0][0] = 0;
maxi = 0;
func(0, 0, 0);
cout << maxi << "\n";
}
}