作者vagrantlike (【傑克】喵嗚)
看板Prob_Solve
標題[問題]zerojudge競賽題目b841:104北二5.骨牌遊戲
時間Sun Jul 17 19:38:37 2016
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
推 yvb: 網址最後的 problemid=b8 應改為 problemid=b841 07/19 14:11
※ 編輯: vagrantlike (61.57.86.164), 07/19/2016 22:51:07
→ vagrantlike: 感謝 連結已修正‘ 07/19 22:52
→ yr: 先把數字區塊找出來再去遞迴找出該區塊可以有幾組如何？ 07/20 21:55
→ yr: size = 2,3 就不用算了 07/20 21:55
→ vagrantlike: to yr:有思考過你提的這種方式 就是典型DFS 07/21 21:39
→ vagrantlike: 找範圍內有幾塊油田題目的變形 只是這時同一塊油田 07/21 21:41
→ vagrantlike: 有相同數字 應該是可行的 07/21 21:42
→ vagrantlike: to chchwy:這段程式碼其實尚未完成 只是想用來記錄 07/21 22:38
→ vagrantlike: 目前想到的解法 他是無法執行的。。。 07/21 22:39
→ yr: 不知道我是不是想得太複雜，區塊可以轉成 graph 07/21 22:42
→ yr: 然後相當於要找該 graph 的 maximum matching 07/21 22:42
→ yr: O(V^2 * E) 07/21 22:44
→ vagrantlike: 剛搜尋graph 的 maximum matching 似乎是可行的 07/21 23:23
→ vagrantlike: 但有殺雞焉用牛刀的感覺 直覺有更簡單的思路可解... 07/21 23:24
※ 編輯: vagrantlike (61.57.86.164), 07/21/2016 23:29:21
推 FRAXIS: 這個圖是 bipartite 的 所以應該很容易算maximum matching 07/22 08:36
→ yr: 嗯嗯，沒發現是 bipartite ，這樣就好解很多 07/22 10:06
→ yr: 研究了一下，跑個 bfs 算奇數層跟偶數層的點數量，取小的 07/22 14:35
→ yr: 這算法不知道有沒忽略特殊情況？ 07/22 14:36
推 FRAXIS: bipartite maximum matching 應該是用 network flow 吧... 07/22 22:22
→ yr: 因為只要算數量， bipartite maximum matching 相當於 07/22 22:46
→ yr: minimum size of a vertex cover ，因為 graph 特性關係，似乎 07/22 22:47
→ yr: 可以直接用 bfs 去求 07/22 22:47
→ yr: graph 特性是指本題產生的 graph 07/22 22:47
→ yr: 查了一下，一般是解西洋棋棋盤拿掉部分，連著的區塊可以 07/23 00:38
→ yr: 完全覆蓋要偶數格跟黑白格數一樣多 07/23 00:40
→ FRAXIS: 但是這題有要完全覆蓋嗎？ 07/23 11:24
→ yr: 我的想法是，可以覆蓋的組數跟顏色少的格子一樣多，不知道這 07/23 11:44
→ yr: 想法正不正確 07/23 11:44
→ yr: 似乎可以用 Hall's theorem 來證明 07/23 12:12
推 FRAXIS: 你有沒有試著找找反例？ 07/23 12:13
推 yllan: 這題最大只有6x6，原po可能想問最基本的暴力法吧～ 07/24 13:10