Baekjoon-16197-두 동전

import sys
import math
input = sys.stdin.readline

N,M = map(int, input().split())

maps = [[] for _ in range(N)]
coins = []
for n in range(N):
    row = input().strip()
    for m in range(M):
        maps[n].append(row[m])
        if row[m] =='o':
            maps[n][m] = '.' # Empty space for coin
            coins.append((n,m))

# Brute-force (4^10) + DFS
def count_on_board(coins):
    count = 0
    for coin in coins:
        if 0<=coin[0]<N and 0<=coin[1]<M:
            count += 1
    return count


def dfs(count, cur_coins):
    if count_on_board(cur_coins) == 1:
        return count
    elif count_on_board(cur_coins) == 0 or count > 10:
        return 11
    
    # left
    left_coins = []
    for i,j in cur_coins:
        if j-1 < 0 or maps[i][j-1]=='.':
            left_coins.append((i,j-1))
        else:
            left_coins.append((i,j))
    # right
    right_coins = []
    for i,j in cur_coins:
        if j+1 == M or maps[i][j+1]=='.':
            right_coins.append((i,j+1))
        else:
            right_coins.append((i,j))
    # up
    up_coins = []
    for i,j in cur_coins:
        if i-1 < 0 or maps[i-1][j]=='.':
            up_coins.append((i-1,j))
        else:
            up_coins.append((i,j))
    # down
    down_coins = []
    for i,j in cur_coins:
        if i+1 == N or maps[i+1][j]=='.':
            down_coins.append((i+1,j))
        else:
            down_coins.append((i,j))

    return min([dfs(count+1, left_coins), dfs(count+1, right_coins), dfs(count+1, up_coins), dfs(count+1, down_coins)])

result = dfs(0, coins)
if result == 11:
    print(-1)
else:
    print(result)