有同學說 "每次當一格列舉完，換下一格跳一個數字時，都想不到方法讓前一格數字再列舉一次" 以下是回信的內容 給同學做個參考 >8---->8----->8---->8--請沿虛線剪開--->8---->8----->8---->8----- 首先你要定義那個遞迴函數能辦到的事 我在助教課有說過 先相信你要寫出來的function能做什麼 再用他去解決小問題 把小問題的答案累積起來 這個大問題就解決了 我的想法如下: int dfs(/* N啦 P啦 S啦 至少都要在這*/, int x, int y){ } 寫完之後 問自己一句 這個函式要解決什麼樣的問題 我的想法是 他會跟我說 在(x, y)還沒填之前 假設已經填的那些值固定 有沒有解 ┌──┬──┬──┬──┬──┐ │ │ │ │ │ │ ├──┼──┼──┼──┼──┤ │ │x,y │▉▉│▉▉│▉▉│ ├──┼──┼──┼──┼──┤ │▉▉│▉▉│▉▉│▉▉│▉▉│ └──┴──┴──┴──┴──┘ 也就是樓上沒寫字的值都確定的情況下 (x, y) 加上剩下畫方塊的所有可能是不是解 那dfs該怎麼回傳呢 我是不是在我(x, y)這個位置所有可能都填的時候 問dfs(...., x, y+1) 如果他是1 那大功告成 馬上return 1 如果是0 那代表革命尚未成功 同志仍需努力 繼續填剩下的可能 那當在dfs(..., x, y)裡面所有可能都填過的時候 dfs(..., x, y + 1)都說辦不到 那代表dfs(..., x, y)針對之前已經填在number裡的值是無解的 return 0就行了 那我們要問的就只是 dfs(..., 0, 0)就行了 他就會幫我們把所有可能都填一遍 至於一些cut的部分 只要記錄目前每個row和每個col已經填的值總和 一旦發現超過了 馬上return 0(因為剩下的怎麼填都不可能) 那在我dfs下一層的時候發現我(x, y)填某個值不可能 那dfs結束時要記得把sumx[x] -= *ptr, sumy[y] -= *ptr 至於怎麼樣換行呢 以及何謂終端條件 我是這樣寫的 int dfs(..., x, y){ if y == N: x++ y = 0 if x == N: return 1 .... } 還要記得 x == N - 1的時候每次都要檢查sumy[y] == S 不是就return 0 y == N - 1的時候每次都要檢查sumx[x] == S 不是就return 0 不知道會不會寫得太亂 請見諒 半夜了總是頭腦不清楚 C2008 TA >8---->8----->8---->8--請沿虛線剪開--->8---->8----->8---->8----- -- 複製貼上沒賺到p幣... --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.30.45