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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
| #include <iostream>
using namespace std;
struct QueueType
{
int opt;
long long sum;
} q[2][13944];
char map[13][13];
int n, m, j, now, last, power[13], pos[2][1594324], tail[2];
inline int Get(const int data, const int index)
{
return data/power[index]%3;
}
inline int Set(int data, const int index, const int value)
{
data = data+(-data/power[index]%3+value)*power[index];
return data;
}
int ChangeRightToLeft(const int opt, int i)
{
int stack = 0;
for (; i < m; ++i)
{
int bit = Get(opt, i);
if (bit == 1)
stack += 1;
else if (bit == 2)
stack -= 1;
if (!stack)
return Set(opt, i, 1);
}
return 0x7FFFFFFF;
}
int ChangeLeftToRight(const int opt, int i)
{
int stack = 0;
for (; i >= 0; --i)
{
int bit = Get(opt, i);
if (bit == 2)
stack += 1;
else if (bit == 1)
stack -= 1;
if (!stack)
return Set(opt, i, 2);
}
return 0x7FFFFFFF;
}
void EnQueue(const int opt, const long long sum)
{
if (j == m-1 && Get(opt, m) != 0)
return;
if (pos[now][opt])
q[now][pos[now][opt]].sum += sum;
else
{
pos[now][opt] = ++tail[now];
q[now][tail[now]].opt = opt;
q[now][tail[now]].sum = sum;
}
}
int main()
{
power[0] = 1;
for (int i = 1; i <= 13; ++i)
power[i] = power[i-1]*3;
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 0; i != n; ++i)
for (int j = 0; j != m; ++j)
{
cin >> map[i][j];
if (map[i][j] == '.')
last = i*m+j;
}
EnQueue(0, 1);
now ^= 1;
for (int i = 0; i != n; ++i)
for (j = 0; j != m; ++j)
{
for (int head = 1; head <= tail[now^1]; ++head)
{
int opt = q[now^1][head].opt;
long long sum = q[now^1][head].sum;
int up = Get(opt, j), left = Get(opt, m);
bool crash = map[i][j] == '*';
if (up == 0 && left == 0) //Case 1
{
if (!crash)
opt = Set(Set(opt, j, 1), m, 2);
EnQueue(opt, sum);
}
else if (up == 2 && left == 1) //Case 2.3
{
if (i*m+j == last)
EnQueue(Set(Set(opt, j, 0), m, 0), sum);
}
else if (crash)
continue;
else if (up == 0 || left == 0) //Case 3
{
EnQueue(Set(Set(opt, j, up+left), m, 0), sum);
EnQueue(Set(Set(opt, m, up+left), j, 0), sum);
}
else if (up == 1 && left == 1) //Case 2.1
{
opt = ChangeRightToLeft(opt, j);
EnQueue(Set(Set(opt, j, 0), m, 0), sum);
}
else if (up == 2 && left == 2) //Case 2.1
{
opt = ChangeLeftToRight(opt, j);
EnQueue(Set(Set(opt, j, 0), m, 0), sum);
}
else //if (up == 1 && left == 2) //Case 2.2
{
EnQueue(Set(Set(opt, j, 0), m, 0), sum);
}
}
now ^= 1;
for (int head = 1; head <= tail[now]; ++head)
pos[now][q[now][head].opt] = 0;
tail[now] = 0;
}
cout << q[now^1][pos[now^1][0]].sum << endl;
}
|
