#include
<
iostream
>
using
namespace
std;
int
a[
5
][
5
];
const
int
d[
5
][
2
]
=
{
0
,
0
,
-
1
,
0
,
0
,
-
1
,
1
,
0
,
0
,
1
};
int
Min;
bool
check(){
for
(
int
i
=
0
;i
<
4
;
++
i)
for
(
int
j
=
0
;j
<
4
;
++
j)
if
(a[i][j]
!=
a[
0
][
0
])
return
0
;
return
1
;
}
void
dfs(
int
x,
int
y,
int
num){
if
(num
>=
Min)
return
;
if
(y
==
4
){
x
++
; y
=
0
;
}
if
(check()){
if
(Min
>
num)
Min
=
num;
return
;
}
if
(x
==
4
)
return
;
dfs(x,y
+
1
,num);
for
(
int
i
=
0
;i
<
5
;
++
i){
int
ax
=
x
+
d[i][
0
],bx
=
y
+
d[i][
1
];
if
(ax
<
0
||
ax
>
3
||
bx
<
0
||
bx
>
3
)
continue
;
a[ax][bx]
=
1
-
a[ax][bx];
}
dfs(x,y
+
1
,num
+
1
);
for
(
int
i
=
0
;i
<
5
;
++
i){
int
ax
=
x
+
d[i][
0
],bx
=
y
+
d[i][
1
];
if
(ax
<
0
||
ax
>
3
||
bx
<
0
||
bx
>
3
)
continue
;
a[ax][bx]
=
1
-
a[ax][bx];
}
}
int
main()
{
char
c;
for
(
int
i
=
0
;i
<
4
;
++
i){
for
(
int
j
=
0
;j
<
4
;
++
j){
c
=
getchar();
if
(c
==
'
b
'
) a[i][j]
=
1
;
else
a[i][j]
=
0
;
}
getchar();
}
Min
=
0xFFFFFFF
;
dfs(
0
,
0
,
0
);
if
(Min
==
0xFFFFFFF
)
printf(
"
Impossible\n
"
);
else
printf(
"
%d\n
"
,Min);
return
0
;
}
posted on 2009-05-28 16:40
xfstart07 阅读(143)
评论(0) 编辑 收藏 引用 所属分类:
代码库