本站遷移

因為我最近租用了網路空間以及網域,
故本站已遷移至新網站~
這邊的資訊已經正在進行搬移的工作~
希望各位可以到新網站去逛XD

New Website:
http://knightzone.org/

搜尋此網誌

2011年3月7日 星期一

[UVa]11195:Another n-Queen Problem

這題要用點bitwise運算的概念,
把原本用陣列記錄列、斜線的放置,
改成用bits來記錄。
由於有點複雜,
我稍微解釋一下程式碼。

y_board[i] = (1<<n)-1;
這裡是讓可以放置皇后的位置用1來記錄,
不可以放置皇后的位置('*')用0來記錄。
那y_board這個陣列是以row(y)來當索引值,
然後col的部份用bits來記錄。
if( s[j] == '*' )
  y_board[i] ^= (1<<j);
這裡就是讓*的位置用1來做XOR運算,
簡單來說就是把j位置的1改成0。
backtracking( n, 0, (1<<n)-1, (1;<<(2*n-1))-
1, (1<<(2*n-1))-1);
這邊把記錄x和記錄兩種斜線的bits丟進去backtracking,
並且x的n個位數都是1,表示目前都可以擺,
而斜線部分的2*n-1個位數也都是1,也表示目前都可以擺。
int nowslash1 = slash1 >> y;
int nowslash2 = slash2 >> (n-y-1);
將目前跑到那行row的斜線號碼全部抓出來,
例如8皇后的第一個row(row[0]),
x+y種類的斜線編號分別是
0+0=0,0+1=1,0+2=2,0+3=3......0+7=7,
也就是說用slash1 >> 0,
這樣即可讓slash1從個位數(2進位)開始的7個位數都剛好對應每一格。
而x-y+(2*n-1)種類的斜線編號分別是
0-0+15=15,0-1+15=14........0-7+15=8,
正好是從高位數(2進位)數過來0位數,
那為了推到個位數(2進位),
就變成slash2 >> 8-0-1,
這樣就可以讓高位數(2進位)的7個位數推到個位數(2進位)來。
int canputqueen = y_board[y] & x & nowslash1 & nowslash2;
用&看看每一格是否能夠放置皇后,
y_board[]檢查是否為*,
x檢查是否這個col被放置皇后,
nowslash1檢查是否這條斜線被放置皇后,
nowslash2檢查另外一種斜線是否被放置皇后,
如果全部都是1,就表示這格可以放置皇后。
while( canputqueen )
{
  xput = canputqueen & (-canputqueen);
  backtracking( n, y+1, x^xput, slash1^(xput<<y), slash2^(xput<<(n-y-1)) );
  canputqueen ^= xput;
}
第一行自己&負自己,可以得到二進位最低位的1,
而我就從這最低位的1開始放置皇后,
那麼x就要記錄放置皇后,
而slash1和slash2也要記錄放置了皇后,
最後再將這個1從canputqueen裡面去除,
再繼續把皇后放在下一個1的位置。
我不知道這樣是否有助於讓你了解這題,
如果還是不了解就底下留言問,
或是先自行推演看看,
或是問其他你認識的人討論這樣XD

這題我剛開始就直接backtracking,
結果時間就爆掉了= ="
後來看到討論都說要用bitmask,
我就用了,
然後一直RE,
結論是我沒加return 0; = =""""""

[C](0.956)

0 意見:

張貼留言