'''
思路:
插头DP,插头状态定义为0,1,2 三种,0表示边上没有插头,1表示插头所在路径是直线,2表示插头所在路径是折线
题目本质是要求所有铺满方格的只包含折线路径的总合法方案数,这个跟求取汉密尔顿回路的方案数其实没有本质区别,
都是插头模型,只不过状态转移的各种情况不一样,都是进行方案累加,整个代码架子是一样的,分情况讨论即可,在
最后一个非障碍物时候,对合法方案进行累加就是最终的答案
'''
from collections import Counter
# 设置边的状态,返回设置之后的状态
def set_edge_state(stat, edge_idx, val) -> int:
stat &= ~(3 << (edge_idx * 2))
stat |= (val << (edge_idx * 2))
return stat
# 获取边的状态
def get_edge_state(stat, edge_idx) -> int:
return (stat >> (edge_idx * 2)) & 3;
m, n = map(int, input().split())
grid = [None] * m
for i in range(m):
grid[i] = input()
if m < n:
gg = [[None] * m for _ in range(n)]
for i in range(n):
for j in range(m):
gg[i][j] = grid[j][i]
grid = gg
m, n = n, m
end_i, end_j = 0, 0
for i in range(m):
for j in range(n):
if grid[i][j] == '_':
end_i, end_j = i, j
ans = 0
hash1, hash2 = Counter(), Counter()
hash1[0] = 1
def add_stat(stat, cnt):
val = hash2[stat]
val += cnt
val %= 20110520
hash2[stat] = val
flag = False
for i in range(m):
if flag:
break
for j in range(n):
#print(i, j, len(hash1))
# 枚举状态(i, j, S) 生成新状态 (i, j+1, S')
for s, cnt in hash1.items():
x, y = get_edge_state(s, j), get_edge_state(s, j+1)
if grid[i][j] == '*':
# 情况1 障碍物且x = 0, y = 0, S状态不变
if x == 0 and y == 0:
add_stat(s, cnt)
else:
if x == 0 and y == 0:
# 情况2 非障碍物, x = 0, y = 0, 三种不同的状态转移
# 2.1 右边和下边加插头
if i + 1 < m and grid[i + 1][j] == '_' and j + 1 < n and grid[i][j + 1] == '_':
new_stat = set_edge_state(s, j, 2)
new_stat = set_edge_state(new_stat, j+1, 2)
add_stat(new_stat, cnt)
# 2.2 下面加插头
if i + 1 < m and grid[i + 1][j] == '_':
new_stat = set_edge_state(s, j, 1)
new_stat = set_edge_state(new_stat, j+1, 0)
add_stat(new_stat, cnt)
# 2.3 右边加插头
if j + 1 < n and grid[i][j + 1] == '_':
new_stat = set_edge_state(s, j, 0)
new_stat = set_edge_state(new_stat, j+1, 1)
add_stat(new_stat, cnt)
elif x == 0 and y == 1:
# 情况3 非障碍物,x = 0, y = 1, 两种状态转移
# 3.1 下面加插头
if i + 1 < m and grid[i + 1][j] == '_':
new_stat = set_edge_state(s, j, 1)
new_stat = set_edge_state(new_stat, j+1, 0)
add_stat(new_stat, cnt)
# 3.2 右边加插头
if j + 1 < n and grid[i][j + 1] == '_':
new_stat = set_edge_state(s, j, 0)
new_stat = set_edge_state(new_stat, j+1, 2)
add_stat(new_stat, cnt)
elif x == 0 and y == 2:
# 情况4 非障碍物,x = 0, y = 2
# 4.1 下面加插头
if i + 1 < m and grid[i + 1][j] == '_':
new_stat = set_edge_state(s, j, 2)
new_stat = set_edge_state(new_stat, j+1, 0)
add_stat(new_stat, cnt)
# 4.2 路径结束
new_stat = set_edge_state(s, j, 0)
new_stat = set_edge_state(new_stat, j + 1, 0)
add_stat(new_stat, cnt)
elif x == 1 and y == 0:
# 情况5 非障碍物,x = 1, y = 0, 两种状态转移
# 5.1 下面加插头
if i + 1 < m and grid[i + 1][j] == '_':
new_stat = set_edge_state(s, j, 2)
new_stat = set_edge_state(new_stat, j + 1, 0)
add_stat(new_stat, cnt)
# 5.2 右边加插头
if j + 1 < n and grid[i][j + 1] == '_':
new_stat = set_edge_state(s, j, 0)
new_stat = set_edge_state(new_stat, j + 1, 1)
add_stat(new_stat, cnt)
elif x == 2 and y == 0:
# 情况6 非障碍物 x = 2, y = 0
# 6.1 右边加插头
if j + 1 < n and grid[i][j + 1] == '_':
new_stat = set_edge_state(s, j, 0)
new_stat = set_edge_state(new_stat, j + 1, 2)
add_stat(new_stat, cnt)
# 6.2 路径结束
new_stat = set_edge_state(s, j, 0)
new_stat = set_edge_state(new_stat, j + 1, 0)
add_stat(new_stat, cnt)
elif x == 1 and y == 1:
# 情况7 非障碍物,x = 1, y = 1 两条直线合并成一个L形路径
new_stat = set_edge_state(s, j, 0)
new_stat = set_edge_state(new_stat, j + 1, 0)
add_stat(new_stat, cnt)
# 其他情况全部不是合法方案
if i == end_i and j == end_j:
for s, cnt in hash2.items():
ans += cnt
flag = True
break
if j != n-1:
hash1, hash2 = hash2, hash1
hash2.clear()
else:
# 一行处理完之后,最右边竖着的边状态肯定是0,下一行开始处理之前这个0要移动到最前面,因为下一行开头的边是竖边
hash1.clear()
for s in hash2.keys():
new_s = s << 2
hash1[new_s] = hash2[s]
hash2.clear()
print(ans)