UVA 00167 - The Sultans Successors

解題觀念

DFS

可以參考我的課程簡報：BFS & DFS
和：Greedy & Graph
關於 DFS 的基本觀念可以參考我的這篇文章：Algorithm - DFS

題目敘述

努比亞的蘇丹沒有子女，他要從有資格的繼承者中挑選一位繼承王位，他希望這個繼承者夠聰明，所以他決定用一個遊戲來測試這些人

他準備了一個西洋棋盤，上面每個格子中均有一個 1 到 99 的數字，他又準備了 8 個皇后棋子，現在必須將 8 個皇后放置到棋盤中，且各皇后彼此不可互相攻擊，然而這樣有不只一種放置方式，而蘇丹要挑選的就是那位可以放置 8 個皇后，並且此 8 個位置的數的和為最大的那位

你的任務就是讀入棋盤上的數，幫蘇丹算出可以放置 8 個皇后的最大的和是多少

西洋棋皇后走法：
圖片來源

Input

輸入的第一列有一個整數 k（k <= 20），代表以下有幾組測試資料（就是幾個棋盤）
每組測試資料有 8 列，每列有 8 個整數（介於 0 到 99），代表棋盤中格子的資料

// Sample Input
2
 1  2  3  4  5  6  7  8
 9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
48 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64
99 92 53 74 69 76 87 98
 9 12 11 12 19 14 15 16
17 14 19 20 29 22 23 24
25 26 57 28 29 30 31 32
33 34 36 76 39 58 39 40
 1 42 43 44 85 46 47 48
58 60 71 82 53 34 55 56
57 58 39 90 61 32 23 44

Output

對每一組測試資料
輸出可以放置 8 個皇后的最大的和是多少
輸出長度為5，靠右對齊一行

// Sample Output
  260
  429

解題觀念簡報參考

DFS

關於 DFS 的基本觀念可以參考我的這篇文章：Algorithm - DFS

Solution Code

#include<bits/stdc++.h>
using namespace std;

int sum;
bool vis[8][8];
int number[8][8];
deque<int> dq[2];

// 八皇后 上下左右斜行皆不重複
int check( int x, int y ){

    for( int i = 0; i < x; i++ ){
        if( dq[1][i] == y ){
            return 0;
        }

        // 如果兩皇后在同一斜線上 其斜率為 1
        // 如果 x2 - x1 == y2 - y1 -> y2 - y1 / x2 - x1 == 1
        if( abs( x - i ) == abs( dq[1][i] - y ) ){
            return 0;
        }
    }
    return 1;
}

void dfs( int q ){

    // 因為每排必至少有一個皇后
    // 所以 x 直接用 q 去代，每行每行去 dfs
    if( dq[0].size() == 8 ){

        int tmp = 0;
        for( int i = 0; i < 8; i++ ){
            tmp += number[ dq[0][i] ][ dq[1][i] ];
        }
        if( tmp > sum ){
            sum = tmp;
        }
        return;
    }

    // 這個 i 是 y 因為 x 已由 q 決定 
    for( int i = 0; i < 8; i++ ){

        // 確認是否此為可放皇后
        if( check( q, i ) ){

            vis[q][i] = true;

            // 把 x y 座標分別放入 deque
            dq[0].push_back(q);
            dq[1].push_back(i);

            // 去算下一排的 q 的 y 會在哪
            dfs( q + 1 );

            // 找完回來要把剛找的那個點設為沒找過
            vis[q][i] = false;

            // 記得把 deque 裡放的點拿出來
            dq[0].pop_back();
            dq[1].pop_back();
        }
    }
}

int main(){
    
    int t;  
    cin >> t;

    while( t-- ){

        memset( number, 0, sizeof(number) );
        memset( vis, false, sizeof(vis) );

        dq[0].clear();
        dq[1].clear();

        for( int i = 0; i < 8; i++ ){
            for( int j = 0; j < 8; j++ ){
                cin >> number[i][j];
            }
        }

        sum = 0;
        dfs( 0 );

        cout << setw(5) << sum << endl;
    }
}