※ 引述《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://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1469441946.A.DCF.html ※ 编辑: DJWS (111.250.57.205), 07/26/2016 07:16:26