PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題]zerojudge競賽題目b841:104北二5.骨牌遊戲

看板Prob_Solve (計算數學 Problem Solving)作者DJWS (...)時間8年前 (2016/07/25 18:19)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串4/4 (看更多)

※ 引述《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