※ 引述《vagrantlike (【傑克】喵嗚)》之銘言：
: http://zerojudge.tw/ShowProblem?problemid=b841
: 對於遞迴題目真的是苦手 T.T
: 想要做的是迭代長方形每個格子點
: 從上下右左的順序依次檢查是否可連成骨牌
: 並遞迴產生所有的狀態
: 再從中選擇骨牌數最多者
: 遇到的問題是
: 1>某點有相鄰相同數字可連成骨牌時如何不選擇該點
: 保留給後面其他點有選擇機會因也許能產生更多骨牌
: 2>遞迴終止條件設定也有問題...
: 3>目前寫法仔細想想根本不是遞迴
: 能否提供建議或想法？謝謝
我幫忙釐清一下好了
1. 依序填寫每個格子點。
(1) 從左到右
(2) 再從上到下
2. 一個格子點，有兩種選擇：放骨牌、不放骨牌。
(1) 放骨牌 ---> 找四個相鄰格子點，是不是有相鄰數字，數字一樣才能放。
[1] 由於 1. 的順序，上方一定之前就嘗試填寫過了。左方也是。
[2] 其實你只需要找右和下！
(2) 不放骨牌 ---> 就略過
實作的時候，我都是這樣一層一層慢慢釐清問題，你可以參考看看。
: int main() {
: int i=0,j = 0;
: while(scanf("%d %d",&H,&W)==2) {
: memset(flag,-2,sizeof(flag));
: for(i=0; i<H; ++i) {
: for(j=0; j<W; ++j) {
: scanf("%d",&board[i][j]);
: }
: }
: for(i=0; i<H; ++i) {
: for(j=0; j<W; ++j) {
: if(flag[i][j]!=-1) {
: dfs(i,j,&cnt);
: }
: }
: }
直接呼叫dfs(0,0)就可以了！從左上角開始填！不需要兩層迴圈～
: printf("%d\n",cnt);
: }
: return 0;
: }
: int dfs(int x, int y,int *id) {
: int i =0,j = 0;
: // 終止條件
if (y == W) {x++; y = 0;} 1.(2). 再由上到下
if (x == H) { 填完了，超過陣列範圍了
: if(x==H-1 && y==W-1) {
: if(*id>maxN)
: maxN = *id;
: return;
: } else {
不要用else啦。因為上面是「遇到特例，馬上return。」的情況。
直接把else大括號去掉，下面程式碼整個往左縮一個tab，比較清爽。
: if(flag[x][y]!=-1) {
: //上,右,下,左
: //?不選？
右和下就夠了
: if(board[x-1][y]==board[x][y] && flag[x-1][y]!=-1) {
: //選擇他
: flag[x][y] = flag[x-1][y] = -1;
: ++*id;
: dfs(x-1,y,*id);
選擇他;
dfs(x, y+1); 填下一格（跟這次選的方向無關）
還原他;
: //不選擇他
: //flag[x][y] = flag[x-1][y] = 0;
: //dfs(x-1,y,--*id);
不選擇他;
dfs(x, y+1); 填下一格（跟這次選的方向無關）
還原他;
: }
: if(board[x][y+1]==board[x][y] && flag[x][y+1]!=-1) {
: //選擇他
: flag[x][y] = flag[x][y+1] = -1;
: ++*id;
: dfs(x,y+1,*id);
: //不選擇他
: //flag[x][y] = flag[x-1][y] = 0;
: //dfs(x,y+1,--*id);
: }
: }
: }
: }
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.250.63.106
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1469441946.A.DCF.html
※ 編輯: DJWS (111.250.57.205), 07/26/2016 07:16:26