作者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://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1468755525.A.420.html
※ 编辑: vagrantlike (61.57.86.164), 07/17/2016 21:43:55
1F：→ FRAXIS: 你给的题目连结不能点.. 07/18 08:33
2F：推 yvb: 网址最後的 problemid=b8 应改为 problemid=b841 07/19 14:11
※ 编辑: vagrantlike (61.57.86.164), 07/19/2016 22:51:07
3F：→ vagrantlike: 感谢 连结已修正‘ 07/19 22:52
5F：→ yr: 先把数字区块找出来再去递回找出该区块可以有几组如何？ 07/20 21:55
6F：→ yr: size = 2,3 就不用算了 07/20 21:55
7F：→ vagrantlike: to yr:有思考过你提的这种方式 就是典型DFS 07/21 21:39
8F：→ vagrantlike: 找范围内有几块油田题目的变形 只是这时同一块油田 07/21 21:41
9F：→ vagrantlike: 有相同数字 应该是可行的 07/21 21:42
10F：→ vagrantlike: to chchwy:这段程式码其实尚未完成 只是想用来记录 07/21 22:38
11F：→ vagrantlike: 目前想到的解法 他是无法执行的。。。 07/21 22:39
12F：→ yr: 不知道我是不是想得太复杂，区块可以转成 graph 07/21 22:42
13F：→ yr: 然後相当於要找该 graph 的 maximum matching 07/21 22:42
14F：→ yr: O(V^2 * E) 07/21 22:44
15F：→ vagrantlike: 刚搜寻graph 的 maximum matching 似乎是可行的 07/21 23:23
16F：→ vagrantlike: 但有杀鸡焉用牛刀的感觉 直觉有更简单的思路可解... 07/21 23:24
※ 编辑: vagrantlike (61.57.86.164), 07/21/2016 23:29:21
18F：推 FRAXIS: 这个图是 bipartite 的 所以应该很容易算maximum matching 07/22 08:36
19F：→ yr: 嗯嗯，没发现是 bipartite ，这样就好解很多 07/22 10:06
20F：→ yr: 研究了一下，跑个 bfs 算奇数层跟偶数层的点数量，取小的 07/22 14:35
21F：→ yr: 这算法不知道有没忽略特殊情况？ 07/22 14:36
23F：推 FRAXIS: bipartite maximum matching 应该是用 network flow 吧... 07/22 22:22
24F：→ yr: 因为只要算数量， bipartite maximum matching 相当於 07/22 22:46
25F：→ yr: minimum size of a vertex cover ，因为 graph 特性关系，似乎 07/22 22:47
26F：→ yr: 可以直接用 bfs 去求 07/22 22:47
27F：→ yr: graph 特性是指本题产生的 graph 07/22 22:47
28F：→ yr: 查了一下，一般是解西洋棋棋盘拿掉部分，连着的区块可以 07/23 00:38
29F：→ yr: 完全覆盖要偶数格跟黑白格数一样多 07/23 00:40
30F：→ FRAXIS: 但是这题有要完全覆盖吗？ 07/23 11:24
31F：→ yr: 我的想法是，可以覆盖的组数跟颜色少的格子一样多，不知道这 07/23 11:44
32F：→ yr: 想法正不正确 07/23 11:44
33F：→ yr: 似乎可以用 Hall's theorem 来证明 07/23 12:12
34F：推 FRAXIS: 你有没有试着找找反例？ 07/23 12:13
35F：推 yllan: 这题最大只有6x6，原po可能想问最基本的暴力法吧～ 07/24 13:10