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,
作者: vagrantlike (【傑克】喵嗚) 2016-07-21 21:39:00
to yr:有思考過你提的這種方式 就是典型DFS找範圍內有幾塊油田題目的變形 只是這時同一塊油田有相同數字 應該是可行的to chchwy:這段程式碼其實尚未完成 只是想用來記錄目前想到的解法 他是無法執行的。。。