Problem:


Problem 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 &times; 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.

Input

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

c11 c12 c13 ... c1w

c21 c22 c23 ... c2w

...

ch1 ch2 ch3 ... chw

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 cyx 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. 

Output

 
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.

Sample Input

7 5
.......
.o...*.
.......
.*...*.
.......
15 13
.......x.......
...o...x....*..
.......x.......
.......x.......
.......x.......
...............
xxxxx.....xxxxx
...............
.......x.......
.......x.......
.......x.......
..*....x....*..
.......x.......
10 10
..........
..o.......
..........
..........
..........
.....xxxxx
.....x....
.....x.*..
.....x....
.....x....
0 0

Output for the Sample Input

8
49
-1



Sample input:
7 5
.......
.o...*.
.......
.*...*.
.......
15 13
.......x.......
...o...x....*..
.......x.......
.......x.......
.......x.......
...............
xxxxx.....xxxxx
...............
.......x.......
.......x.......
.......x.......
..*....x....*..
.......x.......
10 10
..........
..o.......
..........
..........
..........
.....xxxxx
.....x....
.....x.*..
.....x....
.....x....
0 0


Sample output:
8
49
-1

Submission status: Wrong Answer

Solution code:
import sys
from Queue import Queue
R = lambda:map(int,raw_input().split())

MAX = 10000000
dx = [0,1,0,-1]
dy = [1,0,-1,0]

def CalcCost(start):
    global visited
    cost = [[MAX for j in xrange(w)] for i in xrange(h)]
    cost[start[1]][start[0]] = 0
    q = Queue()
    q.put(start)
    while not q.empty():
        p = q.get()
        for i in xrange(4):
            mx,my = p[0]+dx[i],p[1]+dy[i]
            if (0 <= mx < w) and (0 <= my < h) and (visited[my][mx] is False):
            #if (0 <= mx < w) and (0 <= my < h):
                if cost[p[1]][p[0]] + 1 < cost[my][mx]:
                    cost[my][mx] = cost[p[1]][p[0]] + 1
                    q.put((mx,my))
    return cost

while 1:
    w,h = R()
    #cost = [[MAX for j in xrange(w)] for i in xrange(h)]
    visited = [[False for j in xrange(w)] for i in xrange(h)]
    dirt = []
    if not(w or h): break                   
    for i in xrange(h):
        s = raw_input()
        for j in xrange(w):
            if s[j] == '.':
                pass
            elif s[j] == 'o':
                start = (j,i)
            elif s[j] == '*':
                dirt.append((j,i))
            else:
                visited[i][j] = True
                
    distance = 0
    isPossible = True
    while(dirt):
        #print dirt
        c = CalcCost(start)
        tmp = MAX
        for i in xrange(len(dirt)):
            x,y = dirt[i][0],dirt[i][1]
            if c[y][x] == MAX:
                #print -1
                distance = -1
                isPossible = False
                break
            if tmp > c[y][x]:
                start = (x,y)
                tmp = c[y][x]
        if isPossible is False: break
        dirt.remove(start)
        distance += tmp

    print distance

Submission status: Accepted

Solution code:
from collections import deque
dd = [(-1, 0), (0, -1), (1, 0), (0, 1)]
while 1:
    w, h = map(int, raw_input().split())
    if w == 0:
        break
    C = [raw_input() for i in xrange(h)]
    cnt = 0
    mark = {}
    sx = sy = -1
    for i in xrange(h):
        for j in xrange(w):
            if C[i][j] == 'o':
                sx = j; sy = i
            elif C[i][j] == '*':
                mark[j, i] = cnt
                cnt += 1
    ALL = 2**cnt - 1
    dis = {(sx, sy, 0): 0}
    deq = deque()
    deq.append((sx, sy, 0))
    ans = -1
    while deq and ans == -1:
        x, y, state = key = deq.popleft()
        for dx, dy in dd:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < w and 0 <= ny < h and C[ny][nx] != 'x':
                n_state = state
                if C[ny][nx] == '*':
                    n_state |= 1 << mark[nx, ny]
                if n_state == ALL:
                    ans = dis[key] + 1
                    break
                n_key = (nx, ny, n_state)
                if n_key not in dis:
                    dis[n_key] = dis[key] + 1
                    deq.append(n_key)
    print ans

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop
sys.setrecursionlimit(100000)
INF = 10 ** 10

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] != "x":
        visited[ny][nx] = True
        heappush(que, (d + 1, (nx, ny)))
  else:
    return -1

def my_hash(rest):
  return sum([10 ** i for i in rest])

def shortest(fr, rest, edges, dp):
  if rest == set():
    return 0
  if my_hash(rest) in dp[fr]:
    return dp[fr][my_hash(rest)]
  ret = INF
  for d, to in edges[fr]:
    if to in rest:
      score = d + shortest(to, rest - {to}, edges, dp)
      if score < ret:
        ret = score
  dp[fr][my_hash(rest)] = ret
  return ret

def main():
  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] == "*":
          stains.append((x, y))
        elif mp[y][x] == "o":
          start = len(stains)
          stains.append((x, y))
    
    stain_num = len(stains)
    edges = [[] for _ in range(stain_num)]
    D = [[None] * stain_num for _ in range(stain_num)]
    for i in range(stain_num):
      D[i][i] = 0
    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))
        D[i][j] = d
        D[j][i] = d
    if miss_flag:
      print(-1)
      continue


    dp = [{} for _ in range(10)]
    print(shortest(start, {i for i in range(stain_num) if i != start}, edges, dp))
main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
INF = 10 ** 10

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] != "x":
        visited[ny][nx] = True
        heappush(que, (d + 1, (nx, ny)))
  else:
    return -1

def my_hash(rest):
  return sum([10 ** i for i in rest])

def shortest(fr, rest, edges, dp):
  if rest == set():
    return 0
  if my_hash(rest) in dp[fr]:
    return dp[fr][my_hash(rest)]
  ret = INF
  for d, to in edges[fr]:
    if to in rest:
      score = d + shortest(to, rest - {to}, edges, dp)
      if score < ret:
        ret = score
  dp[fr][my_hash(rest)] = ret
  return ret

def main():
  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] == "*":
          stains.append((x, y))
        elif mp[y][x] == "o":
          start = len(stains)
          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

    dp = [{} for _ in range(stain_num)]
    print(shortest(start, {i for i in range(stain_num) if i != start}, edges, dp))

main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
INF = 10 ** 10

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] != "x":
        visited[ny][nx] = True
        heappush(que, (d + 1, (nx, ny)))
  else:
    return -1

def my_hash(rest):
  ret = 0
  for i in rest:
    ret += 10 ** i
  return ret

def shortest(fr, rest, edges, dp):
  if rest == set():
    return 0
  h = my_hash(rest)
  if h in dp[fr]:
    return dp[fr][h]
  ret = INF
  for d, to in edges[fr]:
    if to in rest:
      score = d + shortest(to, rest - {to}, edges, dp)
      if score < ret:
        ret = score
  dp[fr][h] = ret
  return ret

def main():
  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] == "*":
          stains.append((x, y))
        elif mp[y][x] == "o":
          start = len(stains)
          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

    dp = [{} for _ in range(stain_num)]
    print(shortest(start, {i for i in range(stain_num) if i != start}, edges, dp))

main()

Submission status: Accepted

Solution code:
import sys
import math
import bisect
import heapq
import copy
sys.setrecursionlimit(1000000)
from collections import deque
from itertools import permutations

dy = [-1,0,1,0]
dx = [0,1,0,-1]

def main():
    m,n = 0,0
    grid = []
    inf = 1000000007

    def in_the_grid(h,w):
        return 0<=h and h<n  and 0<=w and w<m

    def bfs(i,j):
        dq = deque()
        res = [[inf]*m for _ in range(n)]
        dq.append([i,j,0])
        res[i][j] = 0
        while dq:
            h,w,c = dq.popleft()
            for k in range(4):
                n_h = h+dy[k]
                n_w = w+dx[k]
                if not in_the_grid(n_h,n_w):continue
                if grid[n_h][n_w] == 'x':continue
                if res[n_h][n_w]!=inf:continue
                res[n_h][n_w] = c+1
                dq.append([n_h,n_w,c+1])
        return res

    while True:
        m,n = map(int,input().split())
        if m == 0:break
        grid = []
        dis = []
        ver = []
        for _ in range(n):
            grid.append(input())
        for i in range(n):
            for j in range(m):
                if grid[i][j]=='o':
                    ver.append([i,j])
                    dis.append(bfs(i,j))
        for i in range(n):
            for j in range(m):
                if grid[i][j]=='*':
                    ver.append([i,j])
                    dis.append(bfs(i,j))

        v = len(dis)
        d = [[] for _ in range(v)]
        for i in range(v):
            for j,k in ver:
                d[i].append(dis[i][j][k])

        dp = [[inf]*v for _ in range(1<<v)]
        dp[1][0] = 0
        for bits in range(1<<v):
            for i in range(v):
                if dp[bits][i] == inf:continue
                for j in range(v):
                    if bits&(1<<j):continue
                    dp[bits|(1<<j)][j] = min(dp[bits|(1<<j)][j],
                                             dp[bits][i]+d[i][j])

        ans = inf
        for i in range(1,v):ans = min(ans,dp[(1<<v)-1][i])
        print (ans if ans!=inf else -1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#AOJ F
from collections import deque
from itertools import permutations

dx = [1,0,-1,0]
dy = [0,1,0,-1]

def bfs(sy,sx):
    dist = [[-1]*w for _ in range(h)]#初期化
    que = deque()
    que.append((sy,sx))
    dist[sy][sx] = 0
    while que:
        y,x = que.popleft()
        for i in range(4):
            nx,ny = x+dx[i],y+dy[i]
            if 0 <= nx < w and 0 <= ny < h:
                if dist[ny][nx] < 0 and M[ny][nx] != "x":
                    dist[ny][nx] = dist[y][x] + 1#移動できるなら移動先の距離+1
                    que.append((ny,nx))

    return dist#引数をスタートにした距離のリストを返す

while 1:
    w,h = map(int,input().split())
    if w == 0 and h == 0:
        break
    M = [list(input()) for _ in range(h)]
    p = []
    for i in range(h):
        for j in range(w):
            if M[i][j] == "o":
                p.append((i,j))
                break
    for i in range(h):
        for j in range(w):
            if M[i][j] == "*":
                p.append((i,j))
    #p[0]はスタート位置,その他は汚れの位置
    n = len(p)
    dist = [[float("inf")]*n for _ in range(n)]#スタート及び各汚れ間の最短路
    f = 0
    for i in range(n):
        di = bfs(*p[i])#*listとすると、list[0],list[1],list[2],…と同値
        for j in range(n):
            dist[i][j] = di[p[j][0]][p[j][1]]#dist[i][j]はp[i]をスタートにした場合の汚れまたはスタート間の最短距離
            if dist[i][j] < 0:
                f = 1#もしたどりつけない点があったら終了
                break
    #print(dist)
    if f:
        print(-1)
        continue

    #bitDP
    po = [1<<i for i in range(11)]
    ma = po[n]#ma=11...1 + 1
    dp = [[float("inf")]*(n) for _ in range(ma)]#最後に消したところからの最短路を見る必要があるため2次元(dp[b][i] := 汚れを消した状態がbかつ最後に消した汚れが汚れiの時の最短路)
    dp[1][0] = 0#スタート位置は0
    for b in range(ma):#bは汚れを消した部分を表す
        for j in range(n):
            if b&po[j]:#汚れjが消えていたら終了
                continue
            nb = b|po[j]#新たに汚れjを削除
            for i in range(n):
                if not b&po[i]:#汚れiが消えていないなら終了
                    continue
                #汚れiを最後に消したときb,nbについて比較
                if dp[nb][j] > dp[b][i] + dist[i][j]:#iの後にjを消すほうが最短なら更新
                    dp[nb][j] = dp[b][i] + dist[i][j]
    print(min(dp[ma - 1]))#全部消したときの最短距離を出力

Submission status: Accepted

Solution code:
import sys
from collections import deque
d = [(1,0),(-1,0),(0,1),(0,-1)]
def bfs(sy,sx): #スタートまたは各汚れ間の最短路を計算
    dist = [[-1]*w for i in range(h)]
    dist[sy][sx] = 0
    q = deque([(sy,sx)])
    while q:
        y,x = q.popleft()
        for dy,dx in d:
            y_ = y+dy
            x_ = x+dx
            if 0 <= y_ < h and 0 <= x_ < w:
                if dist[y_][x_] < 0 and s[y_][x_] != "x":
                    dist[y_][x_] = dist[y][x] + 1
                    q.append((y_,x_))
    return dist

po = [1<<i for i in range(11)] #1<<iの前処理(いらないかも??)
while 1:
    w,h = map(int, sys.stdin.readline().split())
    if w == 0:
        break
    s = [sys.stdin.readline() for i in range(h)]
    p = [] #スタート、汚れを保存
    for y in range(h):
        for x in range(w):
            if s[y][x] == "o":
                p.append((y,x))
                break
    for y in range(h):
        for x in range(w):
            if s[y][x] == "*":
                p.append((y,x))
    """↑スタートの座標を常にp[0]に保存したかったからこうやってループを分けた"""
    n = len(p)
    dist = [[float("inf")]*n for i in range(n)] #スタート及び各汚れ間の最短路
    f = 0
    for i in range(n):
        di = bfs(*p[i]) #*listとすると、list[0],list[1],list[2],…と同値なので複数引数の場合にこうやって書くと楽
        for j in range(n):
            dist[i][j] = di[p[j][0]][p[j][1]]
            if dist[i][j] < 0:
                f = 1 #もしたどりつけない点があったら終了
                break
    if f:
        print(-1)
        continue
    """以下bitDP"""
    ma = po[n] #最大状態ma = 111…1+1
    dp = [[float("inf")]*(n) for i in range(ma)] #最後に消したところからの最短路を見る必要があるため2次元(dp[b][i] := 汚れを消した状態がbかつ最後に消した汚れが汚れiの時の最短路)
    dp[1][0] = 0
    for b in range(ma): #b := 汚れを消した部分を表す
        for j in range(n):
            if (b&po[j]):continue #もし汚れjが消えてたら飛ばす
            b_ = b|po[j] #b_ := 新たに汚れjを削除
            for i in range(n):
                if not b&po[i]:continue
                #汚れiを最後に消したときのb,b_について比較
                if dp[b_][j] > dp[b][i]+dist[i][j]:
                    dp[b_][j] = dp[b][i]+dist[i][j]
    print(min(dp[ma-1])) #全部消したときの最短路を出力

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    def f(w,h):
        a = ['x'*(w+2)] + ['x' + S() + 'x' for _ in range(h)] + ['x'*(w+2)]
        e = collections.defaultdict(list)
        st = None
        dst = []
        for i in range(1,h+1):
            for j in range(1,w+1):
                if a[i][j] == 'x':
                    continue
                if a[i][j] == 'o':
                    st = (i,j)
                elif a[i][j] == '*':
                    dst.append((i,j))
                for di,dj in dd:
                    if a[i+di][j+dj] == 'x':
                        continue
                    e[(i,j)].append(((i+di,j+dj), 1))

        def search(s):
            d = collections.defaultdict(lambda: inf)
            d[s] = 0
            q = []
            heapq.heappush(q, (0, s))
            v = collections.defaultdict(bool)
            while len(q):
                k, u = heapq.heappop(q)
                if v[u]:
                    continue
                v[u] = True

                for uv, ud in e[u]:
                    if v[uv]:
                        continue
                    vd = k + ud
                    if d[uv] > vd:
                        d[uv] = vd
                        heapq.heappush(q, (vd, uv))

            return d

        sd = search(st)
        for ds in dst:
            if sd[ds] == inf:
                return -1

        dsd = [search(ds) for ds in dst]
        l = len(dst)
        r = inf
        for ta in itertools.permutations(range(l)):
            t = sd[dst[ta[0]]]
            for i in range(l-1):
                t += dsd[ta[i]][dst[ta[i+1]]]
            if r > t:
                r = t

        return r

    while 1:
        n,m = LI()
        if n == 0 and m == 0:
            break
        rr.append(f(n,m))
        # print('rr', rr[-1])

    return '\n'.join(map(str,rr))


print(main())

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

import sys
import subprocess
import json
import time
import math
import re
import sqlite3
import random
from queue import Queue

dy = [0, 0, 1, -1]
dx = [1, -1, 0, 0]
INF = int(1e20)

class Point:
    def __init__(self, y, x, distance = 0):
        self.y = y
        self.x = x
        self.distance = distance

def ok(y, x):
    global w, h, visited_cnt
    return 0 <= y and y < h and 0 <= x and x < w
        
def bfs(start, goal):
    global w, h, visited_cnt
    q = Queue()
    q.put(start)
    #print("start.distance =", start.distance)
    bfs_visited = [[False for _ in range(w)] for _ in range(h)]
    while not q.empty():
        #print(bfs_visited)
        cur = q.get()
        #print("cur.y =", cur.y, "cur.x =", cur.x)
        if cur.y == goal.y and cur.x == goal.x:
            return cur.distance
        
        for i in range(4):
            next = Point(cur.y + dy[i], cur.x + dx[i], cur.distance + 1)
            if not ok(next.y, next.x): continue
            if bfs_visited[next.y][next.x]: continue
            if c[next.y][next.x] == 'x': continue
            bfs_visited[next.y][next.x] = True
            q.put(next)

    return INF

def dfs(pre):
    global w, h, visited_cnt
    if visited_cnt == points.__len__():
        return 0
        
    res = int(1e80)
    for i in range(points.__len__()):
        if visited[i]: continue
        visited[i] = True
        visited_cnt += 1
        res = min(res, dfs(points[i]) +
                  bfs(pre, points[i])) 
        visited[i] = False
        visited_cnt -= 1
    return res

while True:
    w, h = map(int, input().split())
    if w == 0 and h == 0: exit(0)
    c = [list(input()) for _ in range(h)]
    points = []
    visited = [False] * 15 
    visited_cnt = 0
                  
    for y in range(h):
        for x in range(w):
            if c[y][x] == 'o':
                start = Point(y, x)
            if c[y][x] == '*':
                points.append(Point(y, x))
    #print(points.__len__())
    ret = dfs(start)
    if ret < INF: print(ret)
    else: print(-1)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

import sys
import subprocess
import json
import time
import math
import re
import sqlite3
import random
from queue import Queue

dy = [0, 0, 1, -1]
dx = [1, -1, 0, 0]
INF = int(1e20)

class Point:
    def __init__(self, y, x, distance = 0):
        self.y = y
        self.x = x
        self.distance = distance

def ok(y, x):
    global w, h, visited_cnt
    return 0 <= y and y < h and 0 <= x and x < w
        
def bfs(start, goal):
    global w, h, visited_cnt
    q = Queue()
    q.put(start)
    #print("start.distance =", start.distance)
    bfs_visited = [[False for _ in range(w)] for _ in range(h)]
    while not q.empty():
        #print(bfs_visited)
        cur = q.get()
        #print("cur.y =", cur.y, "cur.x =", cur.x)
        if cur.y == goal.y and cur.x == goal.x:
            return cur.distance
        
        for i in range(4):
            next = Point(cur.y + dy[i], cur.x + dx[i], cur.distance + 1)
            if not ok(next.y, next.x): continue
            if bfs_visited[next.y][next.x]: continue
            if c[next.y][next.x] == 'x': continue
            bfs_visited[next.y][next.x] = True
            q.put(next)

    return INF

def dfs(pre):
    global w, h, visited_cnt
    if visited_cnt == points.__len__():
        return 0
        
    res = int(1e80)
    for i in range(points.__len__()):
        if visited[i]: continue
        visited[i] = True
        visited_cnt += 1
        res = min(res, dfs(points[i]) +
                  bfs(pre, points[i])) 
        visited[i] = False
        visited_cnt -= 1
    return res

while True:
    w, h = map(int, input().split())
    if w == 0 and h == 0: break
    c = [list(input()) for _ in range(h)]
    points = []
    visited = [False] * 15 
    visited_cnt = 0
                  
    for y in range(h):
        for x in range(w):
            if c[y][x] == 'o':
                start = Point(y, x)
            if c[y][x] == '*':
                points.append(Point(y, x))
    #print(points.__len__())
    ret = dfs(start)
    if ret < INF: print(ret)
    else: print(-1)

Submission status: Runtime Error

Solution code:
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))

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop
INF = 10 ** 10

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] != "x":
        visited[ny][nx] = True
        heappush(que, (d + 1, (nx, ny)))
  else:
    return -1

def shortest(fr, rest, edges):
  if rest == set():
    return 0
  ret = INF
  for d, to in edges[fr]:
    if to in rest:
      score = d + shortest(to, rest - {to}, edges)
      if score < ret:
        ret = score
  return ret

def main():
  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] == "*":
          stains.append((x, y))
        elif mp[y][x] == "o":
          start = len(stains)
          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(start, {i for i in range(stain_num) if i != start}, edges))
main()

Submission status: Runtime Error

Solution code:
import sys
from Queue import Queue
R = lambda:map(int,raw_input().split())

MAX = 10000000
dirt = []
dx = [0,1,0,-1]
dy = [1,0,-1,0]

def CalcCost(start):
    global visited
    cost = [[MAX for j in xrange(w)] for i in xrange(h)]
    cost[start[1]][start[0]] = 0
    q = Queue()
    q.put(start)
    while not q.empty():
        p = q.get()
        for i in xrange(4):
            mx,my = p[0]+dx[i],p[1]+dy[i]
            if (0 <= mx < w) and (0 <= my < h) and (visited[my][mx] is False):
            #if (0 <= mx < w) and (0 <= my < h):
                if cost[p[1]][p[0]] + 1 < cost[my][mx]:
                    cost[my][mx] = cost[p[1]][p[0]] + 1
                    q.put((mx,my))
    return cost

while 1:
    w,h = R()
    #cost = [[MAX for j in xrange(w)] for i in xrange(h)]
    visited = [[False for j in xrange(w)] for i in xrange(h)]
    if not(w or h): break                   
    for i in xrange(h):
        s = raw_input()
        for j in xrange(w):
            if s[j] == '.':
                pass
            elif s[j] == 'o':
                start = (j,i)
            elif s[j] == '*':
                dirt.append((j,i))
            else:
                visited[i][j] = True
                
    distance = 0
    isPossible = True
    while(dirt):
        c = CalcCost(start)
        tmp = MAX
        for i in xrange(len(dirt)):
            x,y = dirt[i][0],dirt[i][1]
            if c[y][x] == MAX:
                #print -1
                distance = -1
                isPossible = False
                break
            if tmp > c[y][x]:
                start = (x,y)
                tmp = c[y][x]
        if isPossible is False: break
        dirt.remove(start)
        distance += tmp

    print distance