Test Message

b510: M 皇后 N 城堡

內容

在一個(M+N) x (M+N) 的棋盤上放 M 個皇后 N 個城堡，皇后可走直走斜(八個方向的米字)，城堡只能走直(四個方向的十字)，所有的棋子互相不能吃掉對方。輸出有幾種合法的放法。

輸入

相加不大於 10 的正整數 M 和 N，表示在(M+N) x (M+N) 的棋盤上放置 M 個皇后 N 個城堡。

3 1

輸出

輸出總共有多少種安全的放法，記得答案輸出完加上換行

8

解題思路

用一個二維矩陣模擬棋盤，之後用 dfs 窮舉所有可能性。

每次都找陣列為元素值為 0 的地方放棋子，下棋後將這個棋子可以吃到的位置+1 (城堡十字、皇后米字)，重複此情況直到棋子下完(一個解)或是沒地方放棋子(無法繼續)時返回。

回收棋子時一樣找到他們能吃到的位置將它們-1 減回來。

例外情況

如果先放下城堡，又要在它的斜角處放皇后時，會因為記錄城堡時只調整十字區域的關係而無法正確的判斷，因此當要放皇后時，要反過來往左上和右上區間檢查是否有城堡存在，如果有就跳過這個。

剪枝和優化

  1. 如果下棋時該位置元素 > 0 代表有至少一個棋子能吃到它，所以可以直接跳過這個元素。

  2. 由於城堡和皇后都可以吃橫向的棋子，所以當某一行(row)已經有棋子時就不可能能放另一顆，故放完之後可以直接跳到下一行繼續窮舉。

  3. 因為是由上而下進行判斷，且剪枝時已經把同一 row 的情況剪掉了，所以在規劃二為矩陣時，可以只調整目標位置可以吃到的左下、下、右下區間(城堡只需調整下)。

雖然說棋盤最大值為 10，但似乎沒有極端測資(Ex: 2 皇后 8 城堡)，所以測試時不要用極端測資做測試。

完整程式碼

AC (2ms, 108KB)
#include <stdio.h>

int max, count, table[11][11];

void dfs(int i, int m, int n)
{
    if (i == max)
    {
        count++;
        return;
    }
    for (int j = 0; j < max; j++)
    {
        if (table[i][j])
            continue;
        for (int k = i + 1; k < max; k++)
            table[k][j]++;
        if (m)
        {
            for (int k = i - 1, l = j - 1; k >= 0 && l >= 0; k--, l--)
                if (table[k][l] == -1) goto end;
            for (int k = i - 1, l = j + 1; k >= 0 && l < max; k--, l++)
                if (table[k][l] == -1) goto end;
            for (int k = i + 1, l = j - 1; k < max && l >= 0; k++, l--)
                table[k][l]++;
            for (int k = i + 1, l = j + 1; k < max && l < max; k++, l++)
                table[k][l]++;
            dfs(i + 1, m - 1, n);
            for (int k = i + 1, l = j - 1; k < max && l >= 0; k++, l--)
                table[k][l]--;
            for (int k = i + 1, l = j + 1; k < max && l < max; k++, l++)
                table[k][l]--;
        end:;
        }
        if (n)
            table[i][j] = -1, dfs(i + 1, m, n - 1), table[i][j] = 0;
        for (int k = i + 1; k < max; k++)
            table[k][j]--;
    }
}

int main()
{
    int m, n;
    while (scanf(" %d %d", &m, &n) == 2)
    {
        max = m + n, count = 0;
        dfs(0, m, n);
        printf("%d\n", count);
    }
    return 0;
}