d795.
10401 - Injured Queen Problem
內容
Chess是兩個玩家的棋類遊戲，相信早在六世紀在印度已經流行。然而，在這個問題，我們將不討論關於國際象棋，而我們將討論修改後形成了經典的N皇后問題。我知道你所熟悉的N皇后問題是一個典型的回溯算法。如果你寫的演算法，現在你會發現，有92個可能是 8皇后擺在一個 8x8盤面使的皇后不會互相攻擊。
在這個問題中我們將討論可以將受傷的皇后像一個國王只有在橫向和對角線方向，從目前的立場，但可以達到任何行從當前的位置就像一個正常的chess queen。你必須找到可行安排的數量與這些受傷皇后在特定的（nxn的）盤面（有一些額外的限制），使得沒有兩個皇后互相攻擊。
Fig: Injured Queen at a6 can reach the adjacent grey squares. Queen ate4 can reach adjacent grey squares. The injured queen positions are black and the reachable places are grey. |
輸入說明
輸入文件包含幾行輸入。每一行表示一個盤面的狀態。這些字串的長度是盤面維數 n(0<n<=15).第一個字元表示第一列的狀態，第二個字元表示第二列的狀態。因此，如果第一個字元是2，這意味著我們正在尋找的安排（沒有兩個皇后互相攻擊受傷），其中有受傷女王在A列第2行。行的可能的號碼是1，2，3 ... D和E，F表示第1行，2，3 ... 13，14，15。如果任何列包含'？'這意味著在該列中的受傷女王可以在任何行。因此，一個狀態字符串1？4？？3表示你要找出可能安排在（6x6）棋盤上的總數有多少？另外請注意，不會有無效的輸入。例如，“1？51”是一個無效的輸入，因為一（4 × 4）棋盤上沒有一個第五排。
輸出說明
對每一筆測資輸出一行整數，表示每個盤面可能有的情況。
範例輸入
#1
?????? ??????????????? ???8????? 43?????
範例輸出
#1
2642 22696209911206174 2098208 0
測資資訊：
記憶體限制：
512
MB
提示 ：
感謝某人在一開始的壯烈犧牲.....使這題測資加強(第100001).....
標籤:
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||