[計程] 第六使徒 E罐

[ckclark (大資佬)]

有同學說

"每次當一格列舉完，換下一格跳一個數字時，都想不到方法讓前一格數字再列舉一次"


以下是回信的內容 給同學做個參考


>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
推 demundo:用熊貓眼推
推 benck:sleeping:28 這次有難到
推 lockercho:E罐耶   好懷念的詞
推 averangeall:推洛克人XDD
推 godgunman:推強者助教!!XDD 虛線剪開好酷XD
推 BNMAA:欸欸 你寫成python了
推 benck:10分還沒破半 越來越難了= =
→ benck:    ^的人
→ ckclark:我覺得python的語法蠻適合當pseudo code的