-
Notifications
You must be signed in to change notification settings - Fork 0
/
POJ 1753 Flip Game.cpp
69 lines (65 loc) · 1.4 KB
/
POJ 1753 Flip Game.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <stdio.h>
#include <stdlib.h>
struct point
{
int x; int step; int i;
}p[100002];
int v[100002] = {0};
void bfs(point t, int i, point& b)
{
int x = i / 4, y = i % 4;
b.x = t.x;
b.x = b.x ^ (0x1 << i);
if(x > 0)
b.x = b.x ^ (0x1 << (i - 4));
if(x < 3)
b.x = b.x ^ (0x1 << (i + 4));
if(y > 0)
b.x = b.x ^ (0x1 << (i - 1));
if(y < 3)
b.x = b.x ^ (0x1 << (i + 1));
b.step = t.step + 1;
b.i = i;
return;
}
int main(void)
{
char op[10];
int i, j, f = 0, r = 0, sign = 1;
p[0].x = 0;
p[0].step = 0;
p[0].i = -1;
for(i = 0; i < 4; i++)
{
scanf("%s", op);
for(j = 0; j < 4; j++)
{
if(op[j] == 'b')
{
p[0].x = ((0x1 << (i * 4 + j))| p[0].x);
}
}
}
while(p[r].x !=0 && p[r].x != 0xFFFF)
{
for(i = 0; i < 16; i++)
{
if(p[f].i == i) continue;
r ++;
bfs(p[f], i, p[r]);
if(v[p[r].x]) r--;
else v[p[r].x] = 1;
if(p[r].x == 0 || p[r].x == 0xFFFF) break;
}
if(f == r)
{
sign = 0;
break;
}
f++;
}
if(sign) printf("%d\n", p[r].step);
else printf("Impossible\n");
system("pause");
return 0;
}