d757: 11195 - Another n-Queen Problem
Tags :
Accepted rate : 62人/73人 ( 85% ) [非即時]
評分方式:
Tolerant

最近更新 : 2010-08-12 22:52

Content

相信n-Queen問題對每個研究backtracking的人來講都不陌生,這個問題是要在一個n*n大小的棋盤上擺n個皇后,讓她們不會互相攻擊到。為了讓這個問題更難一點,我們設計了一些障礙物在棋盤上,在這些點上不能放皇后。請留意這些障礙物並不會防止皇后被攻擊。 

在傳統的8-Queen問題中,旋轉與鏡射被視為不同解法,因此我們有92種可能的方式來放置皇后。 

Input
輸入的資料最多包含10筆測試個案,每個測試個案的第一行會有一個整數n(3 < n < 15),接下來的n行代表棋盤資料,點號'.'代表空的盤格,星號'*'代表放有障礙物的盤格。0代表測資結束,請不要對0做任何輸出。
Output
對每筆測試個案,輸出這是第幾個case以及這個case有幾種可能的放置方式。
Sample Input
8
........
........
........
........
........
........
........
........
4
.*..
....
....
....
0
Sample Output
Case 1: 92
Case 2: 1
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 5.0s , <1K
Hint :

據說有種叫做"Bitmask"的東西。

Luckycat譯。

Tags:
出處:
UVa11195 [管理者:
asas (向諸神與地雷醬獻上祈禱)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」