UVA 11085 - Back to the 8-Queens
Contents
本題為中山大學高等程式設計課程作業指定題目之四星題。
題目大意
有一個 8x8 的西洋棋盤，每一行都有一個皇后，給你每個皇后在該行的第幾列，問至少要移動幾個皇后，才能讓他們彼此不會互吃(皇后可以吃垂直、水平或對角線上的棋子)。
輸入範圍
一行代表一筆測試資料，每筆測試資料包括 8 個數字，1 <= 數字 <= 8，第 i 個數字代表第 i 行的皇后在第幾列。
解法
原本覺得可以數學解，想了一下範圍只有 8，可以直接暴搜，對於第 i 個皇后，只搜尋放入後能讓前 i 個符合規則的位置。
要注意的是：當目前的棋子狀態已經符合需求，繼續搜尋下去只會讓步數更多，所以直接 return。
程式碼
#include <bits/stdc++.h>
using namespace std;
bool isOk(int arr[], int id) {
for(int i=0; i<id; i++) {
if (arr[id] == arr[i] || id - i == abs(arr[id] - arr[i])) return false;
}
return true;
}
bool isSolve(int arr[]) {
for(int i=0; i<8; i++)
if (!isOk(arr, i)) return false;
return true;
}
int dfs(int arr[], int id, int step) {
if (isSolve(arr)) {
return step;
}
int temp = arr[id], ans = INT_MAX;
for(int i=1; i<=8; i++) {
arr[id] = i;
if (isOk(arr, id))
ans = min(ans, dfs(arr, id+1, i == temp ? step : step+1));
}
arr[id] = temp;
return ans;
}
int main() {
int arr[8], Case = 1;
while(cin >> arr[0]) {
for(int i=1; i<8; i++) cin >> arr[i];
printf("Case %d: %d\n", Case++, dfs(arr, 0, 0));
}
return 0;
}