Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
暴力枚举DFS水过 282ms#include<stdio.h> #include<string.h> int step,flag,mmap[5][5]; int dir[5][2] = {-1,0, 1,0, 0,0, 0,-1, 0,1}; int check() { for(int i = 0; i < 4; ++i) for(int j = 0; j < 4; ++j) if(mmap[i][j]!=mmap[0][0]) return 0; return 1; } void flip(int x, int y) { for(int i = 0; i < 5; ++i) { int xx = x+dir[i][0]; int yy = y+dir[i][1]; if(xx >= 0&&xx < 4&&yy >= 0&&yy < 4) mmap[xx][yy] = !mmap[xx][yy]; } } void dfs(int x, int y, int deep) { if(deep==step) { flag = check(); return ; } if(x==4||flag)return ; flip(x, y); if(y==3) { dfs(x+1, 0, deep+1); flip(x, y); dfs(x+1, 0, deep); } else { dfs(x, y+1, deep+1); flip(x, y); dfs(x, y+1, deep); } return ; } int main() { char s[5]; while(~scanf("%s", s)) { for(int i = 0; i < 4; ++i) mmap[0][i] = (s[i]=='b'?1:0); for(int i = 1; i < 4; ++i) { scanf("%s", s); for(int j = 0; j < 4; ++j) mmap[i][j] = (s[j]=='b'?1:0); } flag = 0; for(step = 0; step < 17; ++step) { dfs(0, 0, 0); if(flag)break; } flag?printf("%d\n", step):printf("Impossible\n"); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator