有同学说 "每次当一格列举完，换下一格跳一个数字时，都想不到方法让前一格数字再列举一次" 以下是回信的内容 给同学做个参考 >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