首页 > 代码库 > poj 2965 The Pilots Brothers' refrigerator(dfs 枚举 +打印路径)
poj 2965 The Pilots Brothers' refrigerator(dfs 枚举 +打印路径)
链接:poj 2965
题意:给定一个4*4矩阵状态,代表门的16个把手,‘+’代表关,‘-’代表开,当16个把手都为开(即‘-’)时,门才能打开,问至少要几步门才能打开
改变状态规则:选定16个把手中的任意一个,可以改变其本身以及同行同列的状态(即若为开,则变为关,若为关,则变为开),这一次操作为一步.
分析:这题与poj 1753思路差不多,每个把手最多改变一次状态,
所有整个矩阵最多改变16次状态
思路:直接dfs枚举所有状态,直到找到目标状态
但是要打印路径,所有应在dfs时记录路径
注意:可以用位运算操作,这样比较快,若直接判断‘+’‘-’状态变换,很可能超时
<pre name="code" class="cpp">#include<stdio.h> int s[5][5],step,r[20],c[20],flag; int judge() //判断把手是否全开 { int i,j; for(i=0;i<4;i++) for(j=0;j<4;j++) if(s[i][j]) return 0; return 1; } void flip(int i,int j) //改变状态 { int k; s[i][j]=!s[i][j]; for(k=0;k<4;k++){ s[i][k]=!s[i][k]; s[k][j]=!s[k][j]; } } void dfs(int i,int j,int num) { if(num==step){ flag=judge(); return ; } if(flag||i==4) return ; flip(i,j); r[num]=i; //记录路径 c[num]=j; if(j<3) dfs(i,j+1,num+1); else dfs(i+1,0,num+1); flip(i,j); //回溯 if(j<3) dfs(i,j+1,num); else dfs(i+1,0,num); return ; } int main() { int i,j; char t; for(i=0;i<4;i++){ for(j=0;j<4;j++){ scanf("%c",&t); if(t=='+') s[i][j]=1; //用0标记开,1标记关,方便位运算 else s[i][j]=0; } getchar(); } for(step=0;step<=16;step++){ dfs(0,0,0); if(flag) break; } printf("%d\n",step); for(i=0;i<step;i++) printf("%d %d\n",r[i]+1,c[i]+1); return 0; }
poj 2965 The Pilots Brothers' refrigerator(dfs 枚举 +打印路径)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。