poj 1753||poj 2965 枚举+dfs

本文主要是介绍poj 1753||poj 2965 枚举+dfs，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

今天编了1753   2965，枚举和DFS。刚开始自己不太会，思路是看别人的。

一共最多16步即可找到。枚举每一个情况。

 

poj1753

 

#include "iostream" #include "stdio.h" using namespace std; bool map[6][6],f=0; int dis[5][5]={​{0,0},{0,1},{1,0},{0,-1},{-1,0}}; int step; void roll(int row,int col)//翻转 { int i,x,y; for(i=0; i<5; i++) { x=row+dis[i][0]; y=col+dis[i][1]; map[x][y] = !map[x][y]; } } bool Judge()//判断 { int i,j; for(i=1; i<=4; i++) for(j=1; j<=4; j++) if(map[i][j]!=map[1][1]) return 0; return 1; } bool dfs(int row,int col,int dep)//搜索该点 { if(dep == step) { f = Judge(); return 0; } if(f || row == 5) return 1; roll(row,col); if(col<4) dfs(row,col+1,dep+1); else dfs(row+1,1,dep+1); roll(row,col); if(col<4) dfs(row,col+1,dep); else dfs(row+1,1,dep); return 0; } int main() { int i,j; char c; for(i=1; i<=4; i++) { for(j=1; j<=4; j++) { //scanf("%c",&c); cin>>c; if(c=='b') map[i][j]=1; else map[i][j]=0; } } for(step=0; step<=16; step++) { dfs(1,1,0); if(f) break; } if(f) printf("%d/n",step); else printf("Impossible/n"); return 0; }

 

 

poj2965  这个和上面的一样，无非就是要把每个步骤存储在数组当中。

#include "iostream" #include "stdio.h" using namespace std; struct point { int x,y; }r[17]; bool map[6][6],ok=0; int step; void roll(int row,int col) { int i; for(i=1; i<=4; i++) { map[i][col] = !map[i][col]; map[row][i] = !map[row][i]; } map[row][col] = !map[row][col]; } bool Judge() { int i,j; for(i=1; i<=4; i++) for(j=1; j<=4; j++) if(map[i][j]==0) return 0; return 1; } bool dfs(int row,int col,int dep) { if(dep == step) { ok = Judge(); return 0; } if(ok || row == 5) return 1; roll(row,col); if(col<4) { dfs(row,col+1,dep+1); r[dep].x=row; r[dep].y=col; } else { dfs(row+1,1,dep+1); r[dep].x=row; r[dep].y=col; } roll(row,col); if(col<4) dfs(row,col+1,dep); else dfs(row+1,1,dep); return 0; } int main() { int i,j; char c; for(i=1; i<=4; i++) { for(j=1; j<=4; j++) { cin>>c; if(c=='-') map[i][j]=1; else map[i][j]=0; } } for(step=0; step<=16; step++) { dfs(1,1,0); if(ok) break; } if(ok) printf("%d/n",step); for(i=0; i<step; i++) printf("%d %d/n",r[i].x,r[i].y); system("pause"); return 0; }

这篇关于poj 1753||poj 2965 枚举+dfs的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---