首页 > 代码库 > poj1753
poj1753
#include <iostream> using namespace std; #define SIZE 4 char map[SIZE][SIZE]; char map1[SIZE][SIZE]; int Dx[5]={0,0,0,1,-1}; int Dy[5]={0,1,-1,0,0}; int num[16]; int n=0; int minn=20; void fan(int step); bool same(); void fanqi(int x,int y); bool safe(int x,int y); int main() { for(int i=0;i<SIZE;i++) { for(int j=0;j<SIZE;j++) cin >>map[i][j]; } fan(0); if(minn==20) cout <<"Impossible"; else cout <<minn; return 0; } void fan(int step) { int x; int y; if(step==16) { n=0; for(int i=0;i<SIZE;i++) { for(int j=0;j<SIZE;j++) map1[i][j]=map[i][j]; } for(int i=0;i<16;i++) { if(num[i]==1) { x=i/4; y=i%4; fanqi(x,y); n++; } } if(same()) { if(n<minn) minn=n; } return; } num[step]=0; fan(step+1); num[step]=1; fan(step+1); } void fanqi(int x,int y) { int mx; int my; for(int i=0;i<5;i++) { mx=x+Dx[i]; my=y+Dy[i]; if(safe(mx,my)) { if(map1[mx][my]==‘b‘) map1[mx][my]=‘w‘; else map1[mx][my]=‘b‘; } } } bool safe(int x,int y) { bool ret=true; if(x<0||y<0||x>=SIZE||y>=SIZE) ret=false; return ret; } bool same() { bool ret=true; for(int i=0;i<SIZE;i++) { for(int j=0;j<SIZE;j++) { if(map1[i][j]==‘b‘) ret=false; } } if(ret==false) { ret=true; for(int i=0;i<SIZE;i++) { for(int j=0;j<SIZE;j++) { if(map1[i][j]==‘w‘) ret=false; } } } return ret; }
poj1753
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。