# 盤面が非常に小さい、visited管理してDFSにしよう # 問題文では「没収されるときに1つも宝石を持っていない状況」とあるが0個になるのはOKなのか # 動きが上下左右だけというのも書いてない H, W = map(int, input().split()) A = [] for i in range(H): A.append(input()) import sys sys.setrecursionlimit(10**7) def dfs(ch, cw, step, coin): global ans_list, min_step #print('ch', ch, 'cw', cw, 'step', step, 'coin', coin) #print('visited', visited) #print() if step > min_step: return if (ch, cw)==(H-1, W-1): ans_list.append(step) if step < min_step: min_step = step return for dh, dw in d: if 0 <= ch+dh < H and 0 <= cw+dw < W and visited[ch+dh][cw+dw ]==0: if A[ch+dh][cw+dw] == 'o': visited[ch+dh][cw+dw ]=1 dfs(ch+dh, cw+dw, step+1, coin+1) visited[ch+dh][cw+dw ]=0 elif A[ch+dh][cw+dw] == 'x': if coin>=1: visited[ch+dh][cw+dw ]=1 dfs(ch+dh, cw+dw, step+1, coin-1) visited[ch+dh][cw+dw ]=0 d = [[+1, 0], [-1, 0], [0, +1], [0, -1]] min_step = 10**3 ans_list = [] visited = [[0]*W for i in range(H)] visited[0][0] = 1 dfs(0, 0, 0, 1) #print(ans_list) if len(ans_list)>0: min_step = min(ans_list) ans = ans_list.count(min_step) else: ans = 0 print(ans)