一個NxN的棋盤，其中有m對棋子，以連線的方式將每一對棋子都連接起來，并保證棋盤被填滿。（連接僅能橫豎移動，不可交叉，不能跨棋子）例如給定5x5的棋盤：0 0 0 4 30 0 0 0 00 0 1 0 00 0 0 2 04 2 1 3 0其中1、2、3、4分別代表棋子，0代表空位（可連線）。期望連接完成之后：4 4 4 4 34 2 2 2 34 2 1 2 34 2 1 2 34 2 1 3 3其中除了初始點之外的數字都代表線。這里需要注意是“連線”，即每條線必須是有頭有尾有順序的，實際輸出結果中也應包含線的每一段的順序以模擬實際劃線過程，化為圖形界面大概就是下面這樣：問題補充：本人首先自己寫了一個連接算法，是純粹的遞歸嘗試（因為不是求最短路徑，沒有用A star），復雜度太高，對小棋盤還好很快出結果（JS在Chrome上幾秒之內），但從9x9開始效率慘不忍睹（幾十分鐘到幾個小時-_-#），想了一下沒有想到太好的解決方案，求各位幫助啊~~多謝多謝~
1 回答
森林海
TA貢獻2011條經驗 獲得超2個贊
我之前寫過一個連連看的，和你的問題應該一樣，思路是這樣的：
1.先判斷兩點能不能用線段直接連接，能的話問題解決，否則第2步判斷。
2.判斷兩點能不能用僅有一個拐點的折線段連接，能的話問題解決，否則第3步判斷。
3.判斷兩點能不能用僅有兩個拐點的折線段連接，能的話問題解決，否則連接不上。
(注：這里說的都是橫/豎線段)
假設想要連接的兩個點為a、b，算出過a點的橫線段A1和過b點的豎線段B1，算出過a點的豎線段A2和過b點的橫線段B2
第2步的解決方法：
判斷A1、B1能不能相交。不能的話，判斷A2、B2能不能相交。
第3步的解決方法：
判斷是否有豎線段C1能連接A1和B2，判斷是否有橫線段C2能連接A2和B1。
－－－－－－－－－－－－－完－－－－－－－－－－－－－－－－－－－
不知道能不能解決你的問題。
添加回答
舉報
0/150
提交
取消