#13671: 淺見


snakeneedy (蛇~Snake)

School : 國立高雄師範大學附屬高級中學
ID : 7661
IP address : [218.161.41.139]
Last Login :
2021-10-28 16:43:18
a160. 祖靈想要下棋!!!!!!!! -- 祖靈的棋魂!!!! | From: [218.164.210.190] | Post Date : 2018-04-05 15:31

資質駑鈍,對於八皇后問題,都用遞迴去解。我知道 2 種解法:

  1. 模擬棋盤格,放置時考量該點的橫、豎、斜線,沒有其他皇后在
  2. 只紀錄橫、豎、斜線,判斷該點所屬的紀錄沒有皇后

我是用後者,宣告出

bool rows[MAXEDGE], cols[MAXEDGE];
bool LUtoRD[MAXSLOPE], RUtoLD[MAXSLOPE];

其中 LUtoRD 表左上至右下的斜線,RUtoLD 表右上至左下的斜線,四個陣列初始為 false 
(而 MAXEDGE = 11 和 MAXSLOPE = MAXEDGE * 2 - 1 )

從第一列 (i = 0 ) 開始,要放置 (i, j) 前,先判斷 rows[i] , cols[j] , LUtoRD[i - j + N - 1] , RUtoLD[i + j] 是否為 false

可以想一下 LUtoRD 和 RUtoLD 的 index 為什麼這樣用,要用 map<int, int> 取代也行。
(提示範圍 1 - N <= i - j <= N - 1 )

如果可以放,那四項就標記成 true ,接著 i + 1 遞迴下去。

記得做出棋盤格 char board[MAXEDGE][MAXEDGE]; 來存答案;用其他方式也行。

一直放到 i = N 表示所有的皇后都放進去,輸出棋盤格,統計數 + 1。最後輸出統計數即可。

解完這題,可以解看看相關問題(這兩個都不用印出棋盤格)

 
#27379: Re:淺見


d10831523@gapps.fg.tp.edu.tw (廖與僑)

School : 臺北市立第一女子高級中學
ID : 107948
IP address : [203.64.52.40]
Last Login :
2021-11-25 19:37:58
a160. 祖靈想要下棋!!!!!!!! -- 祖靈的棋魂!!!! | From: [203.64.52.40] | Post Date : 2021-09-29 13:31

第二種應該會比較快(?

我也是第二種

 
ZeroJudge Forum