| ||||||||||
| 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