題目連結:
d543: 挑戰極限 Part7:強大的N皇后
題目大意:對於N * N的棋盤,擺上N個皇后且皇后彼此間無法互相攻擊(皇后在西洋棋裡面是走對角線和直線的,也就是米字形。),求擺放的方法數。
思維:
一開始我想到的是最傳統的DFS作法,雖然直觀,但毫無疑問地一定會TLE(超時),當下百思不得其解。
之後,到網路上查詢了一下,發現了兩個高效率的做法。以下分享其中一個:
本來的會TLE是因為在判斷放下這一個皇后會不會被其他皇后攻擊時,花費太長時間所導致。而有一種方法可以加速判斷,而且省記憶體空間。
我們先討論皇后的直線攻擊,由於我們是用DFS+遞迴的概念下去一列一列地一次放一個皇后(或是一行一行做)。因此我們只須考慮其中一方的攻擊(列或行,不會兩者皆需)。而用一個一維陣列就可以做到,只需要儲存哪一列(或行)有放皇后即可。
再來是,對角線的攻擊,而仔細觀察可以發現:對於某一個皇后(C1, C2)來說,他的對角線上所有格子之座標(X, Y),X-C1之絕對值=Y-C2之絕對值,所以也可以用一維陣列儲存。
而這樣便可以大幅加速遞迴的耗時。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大們可以提出來討論。