首页 > 代码库 > POJ 1753 Flip Game (DFS + 枚举)
POJ 1753 Flip Game (DFS + 枚举)
题目:http://poj.org/problem?id=1753
这个题在开始接触的训练计划的时候做过,当时用的是DFS遍历,其机制就是把每个棋子翻一遍,然后顺利的过了,所以也就没有深究。
省赛前一次做PC2遇到了几乎一模一样的题,只不过是把棋盘的界限由4X4改为了5X5,然后一直跑不出结果来,但是当时崔老湿那个队过了,在最后总结的时候,崔老湿就说和这个题一样,不过要枚举第一行进行优化。
我以为就是恢复第一行然后第二行以此类推,不过手推一下结果是6不是4,就知道这个有问题。
问了崔老湿,问了+才,我发现我的思路不正确,应该是用DFS把第一行所有可能出现的情况枚举出来,然后再一行一行的推导。
第一次A的代码:
//DFS #include <stdio.h> #include <stdlib.h> #include <string.h> int MAP[5][5]; int ans = 999999; int pd (void) { int i,k; int ans = 0; for (i = 0;i < 4;i++) for (k = 0;k < 4;k++) ans += MAP[i][k]; if (ans == 0 || ans == 16) return 1; return 0; } int fan (int x,int y) { MAP[x][y] = !MAP[x][y]; if (x - 1 >= 0) MAP[x - 1][y] = !MAP[x - 1][y]; if (y - 1 >= 0) MAP[x][y - 1] = !MAP[x][y - 1]; if (x + 1 < 4) MAP[x + 1][y] = !MAP[x + 1][y]; if (y + 1 < 4) MAP[x][y + 1] = !MAP[x][y + 1]; return 0; } int dfs (int x,int y,int t) { if (pd ()) { if (ans > t) ans = t; return 0; } if (x >= 4 || y >= 4) return 0; int nx = (x + 1) % 4,ny = y + (x + 1) / 4; dfs (nx,ny,t); fan (x,y); dfs (nx,ny,t + 1); fan (x,y); return 0; } int main() { int i,k; for (i = 0;i < 4;i++) { char s[5]; scanf ("%s",s); for (k = 0;k < 4;k++) if (s[k] == 'b') MAP[i][k] = 1; else MAP[i][k] = 0; } dfs (0,0,0); if (ans == 999999) puts ("Impossible"); else printf ("%d\n",ans); return 0; }
用枚举的代码:
//DFS + 枚举 #include <stdio.h> #include <stdlib.h> #include <string.h> int MAP[5][5]; int tMAP[5][5]; int ans = 999999; int pd (int n) { int i; int re = 0; for (i = 0;i < 4;i++) re += tMAP[3][i]; if (n == 1 && re == 0) //防止前三行为1最后一行0以及反之等的特殊情况 return 1; if (n == 2 && re == 4) return 1; return 0; } int fan (int x,int y) { tMAP[x][y] = !tMAP[x][y]; if (x - 1 >= 0) tMAP[x - 1][y] = !tMAP[x - 1][y]; if (y - 1 >= 0) tMAP[x][y - 1] = !tMAP[x][y - 1]; if (x + 1 < 4) tMAP[x + 1][y] = !tMAP[x + 1][y]; if (y + 1 < 4) tMAP[x][y + 1] = !tMAP[x][y + 1]; return 0; } int fanM (int x,int y) { MAP[x][y] = !MAP[x][y]; if (x - 1 >= 0) MAP[x - 1][y] = !MAP[x - 1][y]; if (y - 1 >= 0) MAP[x][y - 1] = !MAP[x][y - 1]; if (x + 1 < 4) MAP[x + 1][y] = !MAP[x + 1][y]; if (y + 1 < 4) MAP[x][y + 1] = !MAP[x][y + 1]; return 0; } int dfs (int x,int y,int t) { if (x >= 1) { //枚举 memcpy (tMAP,MAP,sizeof (MAP)); int tmp = t; int i,k; for (i = 1;i < 4;i++) { for (k = 0;k < 4;k++) { if (tMAP[i - 1][k] == 1) { fan (i,k); tmp++; } } } if (pd (1)) ans = ans < tmp ? ans : tmp; memcpy (tMAP,MAP,sizeof (MAP)); tmp = t; for (i = 1;i < 4;i++) { for (k = 0;k < 4;k++) { if (tMAP[i - 1][k] == 0) { fan (i,k); tmp++; } } } if (pd (2)) ans = ans < tmp ? ans : tmp; return 0; } int ny = (y + 1) % 4,nx = x + (y + 1) / 4; dfs (nx,ny,t); fanM (x,y); dfs (nx,ny,t + 1); fanM (x,y); return 0; } int main() { int i,k; for (i = 0;i < 4;i++) { char s[5]; scanf ("%s",s); for (k = 0;k < 4;k++) if (s[k] == 'b') MAP[i][k] = 1; else MAP[i][k] = 0; } dfs (0,0,0); if (ans == 999999) puts ("Impossible"); else printf ("%d\n",ans); return 0; }
其效果还是很明显的
把所有棋子枚举,转化为只枚举第一行的棋子,就是这个题优化的思路。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。