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

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

看板Prob_Solve (計算數學 Problem Solving)作者vagrantlike (【傑克】喵嗚)時間8年前 (2016/07/17 19:38)推噓6(6推 0噓 29→)

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

http://zerojudge.tw/ShowProblem?problemid=b841 對於遞迴題目真的是苦手 T.T 想要做的是迭代長方形每個格子點從上下右左的順序依次檢查是否可連成骨牌並遞迴產生所有的狀態再從中選擇骨牌數最多者遇到的問題是 1>某點有相鄰相同數字可連成骨牌時如何不選擇該點保留給後面其他點有選擇機會因也許能產生更多骨牌 2>遞迴終止條件設定也有問題... 3>目前寫法仔細想想根本不是遞迴能否提供建議或想法？謝謝 /////////////////////// 以下是我的程式碼 ////////////////////// #include <stdio.h> #include <stdlib.h> int H = 0,W = 0; int board[6][6] = {0}; #include <stdio.h> #include <stdlib.h> int H = 0,W = 0; int board[6][6] = {0}; //-2:初始值；0:先前曾有機會選擇但放棄未選；-1：已被其他相鄰格子選擇過； int flag[6][6] = {-2}; int maxN = -987654321,cnt = 0; 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); } } } printf("%d\n",cnt); } return 0; } int dfs(int x, int y,int *id) { int i =0,j = 0; // 終止條件 if(x==H-1 && y==W-1) { if(*id>maxN) maxN = *id; return; } else { 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); //不選擇他 //flag[x][y] = flag[x-1][y] = 0; //dfs(x-1,y,--*id); } 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); } 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); //不選擇他 //flag[x][y] = flag[x+1][y] = 0; //dfs(x+1,y,--*id); } 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][y-1] = 0; //dfs(x,y-1,--*id); } } } } -- ┌╭─────────╮┬┬┬▄▆██▆▄┬┬╮╮╭╮╮╭╭──┬──╮┐ ┌┼│代號：vagrantlike │┼┼◣▍ ◣ ◢ ▋ ┼╰┼╯╰┼╯│╰┴┼┴╯│┼┐ ├┼│職位：◎偽◎魔術師│┼▁▊▌◤◣◢◥▌▁▂╰┴╮╮ ╭│╭─┴─╮│┼┤ ├┼│等級：等二八星 │◤ █▋ ;; ▍▁◤╭─┤│ ││╰───╯│┼┤ └┼│國王：sseeaa ╭─┼ ▊◥◣ ◢◤ ┼│ │├─╯│╭╯│├○│┼┘ └╰────────╯┴┴┴◤ ◥▅▅◤ ┴┴╯ ╰╰──╰─────╯┘ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.57.86.164 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1468755525.A.420.html ※ 編輯: vagrantlike (61.57.86.164), 07/17/2016 21:43:55

→

FRAXIS

07/18 08:33, , 1^F

07/18 08:33, 1^F

推

yvb

07/19 14:11, , 2^F

07/19 14:11, 2^F

※ 編輯: vagrantlike (61.57.86.164), 07/19/2016 22:51:07

→

vagrantlike

07/19 22:52, , 3^F