output_description: For each map, your program should output a line containing the minimum number
  of moves. If the map includes 'dirty tiles' which the robot cannot reach, your
  program should output -1.
input_description: The input consists of multiple maps, each representing the size and
  arrangement of the room. A map is given in the following format.
  
  > _w h  
  >  _ _c_ 11 _c_ 12 _c_ 13 ... _c_ 1 _w_  
  >  _c_ 21 _c_ 22 _c_ 23 ... _c_ 2 _w_  
  >  ...  
  >  _c_ _h_ 1 _c_ _h_ 2 _c_ _h_ 3 ... _c_ _hw_  
  >  _
  
  The integers _w_ and _h_ are the lengths of the two sides of the floor of the
  room in terms of widths of floor tiles. _w_ and _h_ are less than or equal to
  20. The character _c yx_ represents what is initially on the tile with
  coordinates (_x, y_) as follows.
  
  > '`.`' : a clean tile  
  >  '`*`' : a dirty tile  
  >  '`x`' : a piece of furniture (obstacle)  
  >  '`o`' : the robot (initial position)  
  >
  
  In the map the number of 'dirty tiles' does not exceed 10. There is only one
  'robot'.
  
  The end of the input is indicated by a line containing two zeros.
attempt: from heapq import heappush, heappop
  
  INF = 10**20
  
  direct = ((0, -1), (0, 1), (-1, 0), (1, 0))
  
  
  def dist(fr, to, mp):
      que = []
      heappush(que, (0, fr))
      visited = [[False] * len(mp[0]) for _ in range(len(mp))]
      visited[fr[1]][fr[0]] = True
      while que:
          d, point = heappop(que)
          x, y = point
          for dx, dy in direct:
              nx, ny = x + dx, y + dy
              if (nx, ny) == to:
                  return d + 1
              if not visited[ny][nx] and mp[ny][nx] == ".":
                  visited[ny][nx] = True
                  heappush(que, (d + 1, (nx, ny)))
      else:
          return -1
  
  
  def shortest(fr, rest, edges):
      if rest == []:
          return 0
      ret = INF
      for d, to in edges[fr]:
          if to in rest:
              ret = min(ret, d + shortest(to, [i for i in rest if i != to], edges))
      return ret
  
  
  while True:
      w, h = map(int, input().split())
      if w == 0:
          break
      mp = ["x" + input() + "x" for _ in range(h)]
      mp.insert(0, "x" * (w + 2))
      mp.append("x" * (w + 2))
  
      stains = []
      for y in range(1, h + 1):
          for x in range(1, w + 1):
              if mp[y][x] in ("*", "o"):
                  stains.append((x, y))
  
      stain_num = len(stains)
      edges = [[] for _ in range(stain_num)]
      miss_flag = False
      for i in range(stain_num):
          for j in range(i + 1, stain_num):
              fr = stains[i]
              to = stains[j]
              d = dist(fr, to, mp)
              if d == -1:
                  miss_flag = True
              edges[i].append((d, j))
              edges[j].append((d, i))
      if miss_flag:
          print(-1)
          continue
  
      print(shortest(0, [i for i in range(1, stain_num)], edges))
  
problem_description: F: Cleaning Robot
  
  Here, we want to solve path planning for a mobile robot cleaning a rectangular
  room floor with furniture.
  
  Consider the room floor paved with square tiles whose size fits the cleaning
  robot (1 × 1). There are 'clean tiles' and 'dirty tiles', and the robot can
  change a 'dirty tile' to a 'clean tile' by visiting the tile. Also there may
  be some obstacles (furniture) whose size fits a tile in the room. If there is
  an obstacle on a tile, the robot cannot visit it. The robot moves to an
  adjacent tile with one move. The tile onto which the robot moves must be one
  of four tiles (i.e., east, west, north or south) adjacent to the tile where
  the robot is present. The robot may visit a tile twice or more.
  
  Your task is to write a program which computes the minimum number of moves for
  the robot to change all 'dirty tiles' to 'clean tiles', if ever possible.
samples: [{"input": "5\n    .......\n    .o...*.\n    .......\n    .*...*.\n    .......\n    15 13\n    .......x.......\n    ...o...x....*..\n    .......x.......\n    .......x.......\n    .......x.......\n    ...............\n    xxxxx.....xxxxx\n    ...............\n    .......x.......\n    .......x.......\n    .......x.......\n    ..*....x....*..\n    .......x.......\n    10 10\n    ..........\n    ..o.......\n    ..........\n    ..........\n    ..........\n    .....xxxxx\n    .....x....\n    .....x.*..\n    .....x....\n    .....x....\n    0 0", "output": "49\n    -1"}]