首页 > 代码库 > POJ 2965 The Pilots Brothers' refrigerator (DFS)
POJ 2965 The Pilots Brothers' refrigerator (DFS)
题目:http://poj.org/problem?id=2965
也是以前就做过的题目,这次居然遇到了问题搞了一天。
关于最小步骤很容易就出来,DFS就可以,但是每一步是什么怎么也出不来了
DFS本质就是利用栈暴力,当出现正确结果的时候其过程都在栈中,我一直努力想还原这个栈,未果
然后思路大乱,然后问了RE,才发现根本不用这么麻烦,只需要建个存储步骤数组,在改变元素的时候记录并不停更新就好啦。
然后就简单的解决了问题;= =
#include <stdio.h> #include <stdlib.h> #include <string.h> int MAP[5][5]; int ans = 999999; int zx[1000],zy[1000],ansx[1000],ansy[1000]; int pd (void) { int re = 0; int i,k; for (i = 0;i < 4;i++) for(k = 0;k < 4;k++) re += MAP[i][k]; if (re == 0) return 1; return 0; } int fan (int x,int y) { int i; for (i = 0;i < 4;i++) MAP[i][y] = !MAP[i][y]; for (i = 0;i < 4;i++) MAP[x][i] = !MAP[x][i]; MAP[x][y] = !MAP[x][y]; return 0; } int dfs (int x,int y,int t) { if (pd ()) { if (ans > t) { ans = t; for (int i = 0;i < ans;i++) { ansx[i] = zx[i]; ansy[i] = zy[i]; } } return 0; } if (x > 3 || y > 3) return 0; int ny = (y + 1) % 4,nx = x + (y + 1) / 4; dfs (nx,ny,t); fan (x,y); zx[t] = x + 1; //记录在第t步打开或关了了哪个门 zy[t] = y + 1; 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] == '+') MAP[i][k] = 1; else MAP[i][k] = 0; } dfs (0,0,0); printf ("%d\n",ans); for (i = 0;i < ans;i++) printf ("%d %d\n",ansx[i],ansy[i]); return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。