Problem:


城の堀

いま、忍者が城外から天守閣に忍び入ろうと計画を立てています。この忍者は地面を走ったり、堀の中を泳いだりすることは難なくできますが、堀から這い上がることはとても苦手なので、忍者は堀に入る回数をできるだけ少なくしたいと考えています。

お城の見取図を入力とし、城外から天守閣に至るまでに、堀から這い上がらなくてはならない最小回数を出力するプログラムを作成して下さい。お城の見取図は二次元格子として与えられます。見取り図に描かれた記号には、天守閣の位置を示す「&」と堀の位置を示す「#」の位置が記され、そのほかの地点には「.」（半角ピリオド）が記されています。なお、お城には天守閣は一つだけあるものとし、忍者は走ったり泳いだりして移動するときに東西南北方向に1マスずつ移動するものとし、斜めには移動しません。

Input

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロ２つの行で示されます。各データセットは以下の形式で与えられます。

n m
c1,1c1,2...c1,n
c2,1c2,2...c2,n
:
cm,1cm,2...cm,n

１行目に見取図の東西の幅 n と 南北の幅 m (1 ≤ n, m ≤ 100) が与えられる。続くm 行に見取り図の i 行目の情報が与えられる。各情報は記号「&」、「#」、「.」からなる長さ n の文字列である。

データセットの数は 50 を越えない。

Output

データセットごとに堀から這い上がらなくてはならない最小回数（整数）を１行に出力します。

Sample Input

5 5
.###.
#...#
#.&.#
#...#
.###.
18 15
..####....####....
####..####....####
#...............##
.#.############.##
#..#..........#.##
.#.#.########.#.##
#..#.#......#.#.##
.#.#....&...#.#.##
#..#........#.#.##
.#.#.########.#.##
#..#..........#.##
.#.############.##
#...............##
.#################
##################
9 10
#########
........#
#######.#
#.....#.#
#.###.#.#
#.#&#.#.#
#.#...#.#
#.#####.#
#.......#
#########
9 3
###...###
#.#.&.#.#
###...###
0 0

Output for the Sample Input

1
2
0
0



Sample input:
5 5
.###.
#...#
#.&.#
#...#
.###.
18 15
..####....####....
####..####....####
#...............##
.#.############.##
#..#..........#.##
.#.#.########.#.##
#..#.#......#.#.##
.#.#....&...#.#.##
#..#........#.#.##
.#.#.########.#.##
#..#..........#.##
.#.############.##
#...............##
.#################
##################
9 10
#########
........#
#######.#
#.....#.#
#.###.#.#
#.#&#.#.#
#.#...#.#
#.#####.#
#.......#
#########
9 3
###...###
#.#.&.#.#
###...###
0 0


Sample output:
1
2
0
0

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop

while True:
  n, m = map(int, input().split())
  if n == 0: break

  mp = ["X" + input() + "X" for _ in range(m)]
  mp.insert(0, "X" * (n + 2))
  mp.append("X" * (n + 2))
  
  que = []
  visited = [[False] * (n + 2) for _ in range(m + 2)]
  for i in range(1, n + 1):
    c1 = 1 if mp[1][i] == "#" else 0
    c2 = 1 if mp[m][i] == "#" else 0
    heappush(que, (c1, (i, 1)))
    heappush(que, (c2, (i, m)))
    visited[1][i] = True
    visited[m][i] = True
  for i in range(1, m + 1):
    c1 = 1 if mp[i][1] == "#" else 0
    c2 = 1 if mp[i][n] == "#" else 0
    heappush(que, (c1, (1, i)))
    heappush(que, (c2, (n, i)))
    visited[i][1] = True
    visited[i][n] = True
  
  direct = ((0, 1), (0, -1), (1, 0), (-1, 0))
  reached = False
  
  while que and not reached:
    cost, point = heappop(que)
    x, y = point
    for dx, dy in direct:
      newx, newy = x + dx, y + dy
      if not visited[newy][newx]:
        visited[newy][newx] = True
        if mp[newy][newx] == "&":
          print(cost)
          reached = True
          break
        if mp[newy][newx] == "#":
          heappush(que, (cost + 1, (newx, newy)))
        elif mp[newy][newx] == ".":
          heappush(que, (cost, (newx, newy)))

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop

while True:
  n, m = map(int, input().split())
  if n == 0: break

  mp = ["X" + input() + "X" for _ in range(m)]
  mp.insert(0, "X" * (n + 2))
  mp.append("X" * (n + 2))
  
  que = []
  visited = [[False] * (n + 2) for _ in range(m + 2)]
  for i in range(1, n + 1):
    c1 = 1 if mp[1][i] == "#" else 0
    c2 = 1 if mp[m][i] == "#" else 0
    heappush(que, (c1, (i, 1)))
    heappush(que, (c2, (i, m)))
    visited[1][i] = True
    visited[m][i] = True
  for i in range(1, m + 1):
    c1 = 1 if mp[i][1] == "#" else 0
    c2 = 1 if mp[i][n] == "#" else 0
    heappush(que, (c1, (1, i)))
    heappush(que, (c2, (n, i)))
    visited[i][1] = True
    visited[i][n] = True
  
  direct = ((0, 1), (0, -1), (1, 0), (-1, 0))
  reached = False
  
  while que and not reached:
    cost, point = heappop(que)
    x, y = point
    if mp[y][x] == "&":
      print(cost)
      break
    for dx, dy in direct:
      newx, newy = x + dx, y + dy
      if not visited[newy][newx]:
        visited[newy][newx] = True
        if mp[newy][newx] == "&":
          print(cost)
          reached = True
          break
        if mp[newy][newx] == "#":
          heappush(que, (cost + 1, (newx, newy)))
        elif mp[newy][newx] == ".":
          heappush(que, (cost, (newx, newy)))

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop

while True:
  n, m = map(int, input().split())
  if n == 0: break

  mp = ["X" + input() + "X" for _ in range(m)]
  mp.insert(0, "X" * (n + 2))
  mp.append("X" * (n + 2))
  
  que = []
  visited = [[False] * (n + 2) for _ in range(m + 2)]
  sur_flag = False
  for i in range(1, n + 1):
    if mp[1][i] =="&" or mp[m][i] == "&":
      sur_flag = True
      break
    c1 = 1 if mp[1][i] == "#" else 0
    c2 = 1 if mp[m][i] == "#" else 0
    heappush(que, (c1, (i, 1)))
    heappush(que, (c2, (i, m)))
    visited[1][i] = True
    visited[m][i] = True
  
  for i in range(1, m + 1):
    if mp[i][1] == "&" or mp[i][n] == "&":
      sur_flag = True
      break
    c1 = 1 if mp[i][1] == "#" else 0
    c2 = 1 if mp[i][n] == "#" else 0
    heappush(que, (c1, (1, i)))
    heappush(que, (c2, (n, i)))
    visited[i][1] = True
    visited[i][n] = True
  
  if sur_flag:
    print(0)
    continue
  
  direct = ((0, 1), (0, -1), (1, 0), (-1, 0))
  reached = False
  
  while que and not reached:
    cost, point = heappop(que)
    x, y = point
    for dx, dy in direct:
      newx, newy = x + dx, y + dy
      if not visited[newy][newx]:
        visited[newy][newx] = True
        if mp[newy][newx] == "&":
          print(cost)
          reached = True
          break
        elif mp[newy][newx] == "#":
          heappush(que, (cost + 1, (newx, newy)))
        elif mp[newy][newx] in (".", "&"):
          heappush(que, (cost, (newx, newy)))

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heapify
from itertools import product

def solve():
    hq = [(0, y, x) for y, x in product(xrange(m), xrange(n)) 
          if not(0 < y < m - 1 and 0 < x < n - 1)]
    heapify(hq)
    while len(hq) != 0:
        cost, cy, cx = heappop(hq)
        if field[cy][cx] == "&":
            return cost
        if memo[cy][cx] <= cost:
            continue
        memo[cy][cx] = cost
        for dx, dy in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            ny, nx = cy + dy, cx + dx
            if 0 <= ny < m and 0 <= nx < n:
                if field[ny][nx] == "." and field[cy][cx] == "#":
                    heappush(hq, (cost + 1, ny, nx))
                else:
                    heappush(hq, (cost, ny, nx))
    return None

while True:
    n, m = map(int, raw_input().split())
    if n | m == 0:
        break
    memo = [[1 << 20] * n for _ in xrange(m)]
    field = [raw_input() for _ in xrange(m)]    
    print solve()

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heapify
from itertools import product

def solve():
    hq = [(0, y, x) for y, x in product(xrange(m), xrange(n)) 
          if not(0 < y < m - 1 and 0 < x < n - 1)]
    heapify(hq)
    while len(hq) != 0:
        cost, cy, cx = heappop(hq)
        if field[cy][cx] == "&":
            return cost
        if memo[cy][cx] <= cost:
            continue
        memo[cy][cx] = cost
        for dx, dy in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            ny, nx = cy + dy, cx + dx
            if 0 <= ny < m and 0 <= nx < n:
                if field[ny][nx] == "." and field[cy][cx] != ".":
                    heappush(hq, (cost + 1, ny, nx))
                else:
                    heappush(hq, (cost, ny, nx))
    return None

while True:
    n, m = map(int, raw_input().split())
    if n | m == 0:
        break
    memo = [[1 << 20] * n for _ in xrange(m)]
    field = [raw_input() for _ in xrange(m)]    
    print solve()

Submission status: Memory Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0156

"""
import sys
from sys import stdin
from collections import deque
input = stdin.readline


def bfs(field, sx, sy, d=None, q=[]):
    """
    ??????????????°???????????°??????????????§??????????????????
    :param field:
    :param sx: ??????????????°????????§?¨?
    :param sy:
    :return: ????????????????????´???????????§????????¢
    """
    # ????????????????§????????????´????????§?¨?????????????
    dy = [-1, 1, 0, 0]
    dx = [0, 0, -1, 1]
    # ??°???????????????(?§????????????£????????????????????????????????§??????????????¨)
    Y = len(field)
    X = len(field[0])
    if d == None:
        d = [[float('inf')] * X for _ in range(Y)] #  ??????????????°?????????????????¢???INF??§?????????
    moats = set()                   # ????????§???????????????????????§?¨?

    # ???????????????????????????????????°???????????´????????°????????§????????¢????±???????
    Q = deque()
    if q == []:
        Q.append((sx, sy))
        d[sy][sx] = 0               #  ??????????????°??????????????????0
    else:
        Q.extend(q)
    while Q:
        cx, cy = Q.popleft()        #  ?????¨??°?????§?¨?
        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]
            # ?§?????????? ??°????????????????????????????????? and ?£?????????£???????????? and ??¢?????¢?´¢?????§?????? ??´???
            if (not 0 <= nx < X) or (not 0 <= ny < Y):
                return True, moats, d
            elif d[ny][nx] == float('inf'):
                if field[ny][nx] == '#':
                    moats.add((nx, ny))
                else:
                    Q.append((nx, ny))
                    d[ny][nx] = d[cy][cx] + 1
    return False, moats, d


def fill_moat(field, moats):
    # ??¢??\???????????¨????????????????????£??????????????????'^'??§?????????
    dy = [-1, 1, 0, 0]
    dx = [0, 0, -1, 1]
    # ??°???????????????(?§????????????£????????????????????????????????§??????????????¨)
    Y = len(field)
    X = len(field[0])

    while moats:
        cx, cy = moats.pop()        #  ?????¨??°?????§?¨?
        field[cy][cx] = '^'
        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]
            if (0 <= nx < X) and (0 <= ny < Y):
                if field[ny][nx] == '#':
                    moats.add((nx, ny))


def solve(field):
    # ??????????????°???(????????£: &)?????????
    start = (0, 0)
    for y, row in enumerate(field):
        if '&' in row:
            start = (row.index('&'), y)

    sx, sy = start
    climb = 0                   #  ???????????????????????° = ??????????????????????????°
    d = None
    q = []
    while True:
        res, moats, d = bfs(field, sx, sy, d, q) #  ????????£????????°?????????????????????????¢????
        q = list(moats)
        if res is False:
            climb += 1
            fill_moat(field, moats) #  ??¢??\?????????????????????
        else:
            break
    return climb


def main(args):
    while True:
        n, m = map(int, input().split())
        if n == 0 and m == 0:
            break

#        data = [
#         '.###.',
#         '#...#',
#         '#.&.#',
#         '#...#',
#         '.###.'
#        ]

        data = [input().strip('\n') for _ in range(m)]
        field = [list(x) for x in data] #  data????????????????????????????????????????????????
        result = solve(field)
        print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
def ReadMap(n, m):
  Map = [0] * m
  for i in range(m):
    a = raw_input()
    b = list(a)
    if a.count('&')>0:
      j = a.index('&')
      PosCas = [j, i]
      b[j] = '.'
    Map[i] = b
  return Map, PosCas

def fill(SP, c1, c2):
  for x, y in SP:
    if not (0 <= x < n and 0 <= y < m):
      continue
    if Map[y][x]!=c1:
      continue
    if x in [0, n-1] or y in [0, m-1]:
      return 1
    Map[y][x] = c2
    SP += ([[x+1, y] , [x-1, y], [x, y+1], [x, y-1]])
  return 0

def PrintMap():
  for e in Map:
    print "".join(e)
  print
  return

while 1:
  n, m = map(int,raw_input().split())
  if n == m == 0: break
  Map, PosCas = ReadMap(n, m)
  c = 0
#  PrintMap()
  while 1:
    SP = [PosCas]
    if fill(SP, '.', '#'): break
#    PrintMap()
    c += 1
    if fill(SP, '#', '.'): break
#    PrintMap()
  print c

Submission status: Accepted

Solution code:
def ReadMap(n, m):
  Map = [0] * m
  for i in range(m):
    a = raw_input()
    b = list(a)
    if a.count('&')>0:
      j = a.index('&')
      PosCas = [j, i]
      b[j] = '.'
    Map[i] = b
  return Map, PosCas

def fill(SP, c1, c2):
  for x, y in SP:
    try:
      if Map[y][x]!=c1:continue
    except: continue
    if x in [0, n-1] or y in [0, m-1]:
      return 1
    Map[y][x] = c2
    SP += ([[x+1, y] , [x-1, y], [x, y+1], [x, y-1]])
    
  return 0

def PrintMap():
  for e in Map:
    print "".join(e)
  print
  return

while 1:
  n, m = map(int,raw_input().split())
  if n == m == 0: break
  Map, PosCas = ReadMap(n, m)
  c = 0
#  PrintMap()
  while 1:
    SP = [PosCas]
    if fill(SP, '.', '#'): break
#    PrintMap()
    c += 1
    if fill(SP, '#', '.'): break
#    PrintMap()
  print c

Submission status: Accepted

Solution code:
def ReadMap(n, m):
  Map = [0] * m
  for i in range(m):
    a = raw_input()
    b = map(int,list(a.replace('.','0').replace('#','1').replace('&','2')))
    if a.count('&')>0:
      j = a.index('&')
      PosCas = [j, i]
      b[j] = 0
    Map[i] = b
  return Map, PosCas

def fill(SP, c1, c2):
  for x, y in SP:
    try:
      if Map[y][x]!=c1:continue
    except: continue
    if x in [0, n-1] or y in [0, m-1]: return 1
    Map[y][x] = c2
    SP += ([[x+1, y] , [x-1, y], [x, y+1], [x, y-1]])
  return 0

while 1:
  n, m = map(int, raw_input().split())
  if n == m == 0: break
  Map, PosCas = ReadMap(n, m)
  c = 0
  while 1:
    SP = [PosCas]
    if fill(SP, 0, 1): break
    c += 1
    if fill(SP, 1, 0): break
  print c

Submission status: Accepted

Solution code:
def ReadMap(n, m):
  Map = [0] * m
  for i in range(m):
    a = raw_input()
    b = list(a)
    if a.count('&')>0:
      j = a.index('&')
      PosCas = [j, i]
      b[j] = '.'
    Map[i] = b
  return Map, PosCas

def fill(SP, c1, c2):
  for x, y in SP:
    try:
      if Map[y][x] != c1: continue
    except: continue
    if x in [0, n-1] or y in [0, m-1]: return 1
    Map[y][x] = c2
    SP += [[x+1, y], [x-1, y], [x, y+1], [x, y-1]]
  return 0

while 1:
  n, m = map(int, raw_input().split())
  if n == m == 0: break
  Map, PosCas = ReadMap(n, m)
  c = 0
  while 1:
    SP = [PosCas]
    if fill(SP, '.', '#'): break
    c += 1
    if fill(SP, '#', '.'): break
  print c

Submission status: Accepted

Solution code:
def ReadMap(n, m):
  Map = {}
  for i in range(m):
    a = raw_input()
    b = list(a)
    if a.count('&')>0:
      j = a.index('&')
      PosCas = [j, i]
      b[j] = '.'
    Map[i] = b
  return Map, PosCas

def fill(SP, c1, c2):
  for x, y in SP:
    try:
      if Map[y][x] != c1: continue
    except: continue
    if x in [0, n-1] or y in [0, m-1]: return 1
    Map[y][x] = c2
    SP += [[x+1, y], [x-1, y], [x, y+1], [x, y-1]]
  return 0

while 1:
  n, m = map(int, raw_input().split())
  if n == m == 0: break
  Map, PosCas = ReadMap(n, m)
  c = 0
  while 1:
    SP = [PosCas]
    if fill(SP, '.', '#'): break
    c += 1
    if fill(SP, '#', '.'): break
  print c

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0156

"""
import sys
from sys import stdin
from collections import deque
input = stdin.readline


def bfs(field, sx, sy):
    """
    ??????????????°???????????°??????????????§??????????????????
    :param field:
    :param sx: ??????????????°????????§?¨?
    :param sy:
    :return: ????????????????????´???????????§????????¢
    """
    # ????????????????§????????????´????????§?¨?????????????
    dy = [-1, 1, 0, 0]
    dx = [0, 0, -1, 1]
    # ??°???????????????(?§????????????£????????????????????????????????§??????????????¨)
    Y = len(field)
    X = len(field[0])
    d = [[float('inf')] * X for _ in range(Y)] #  ??????????????°?????????????????¢???INF??§?????????
    moats = set()                   # ????????§???????????????????????§?¨?

    # ???????????????????????????????????°???????????´????????°????????§????????¢????±???????
    Q = deque()
    Q.append((sx, sy))
    d[sy][sx] = 0               #  ??????????????°??????????????????0
    while Q:
        cx, cy = Q.popleft()        #  ?????¨??°?????§?¨?
        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]
            # ?§?????????? ??°????????????????????????????????? and ?£?????????£???????????? and ??¢?????¢?´¢?????§?????? ??´???
            if (not 0 <= nx < X) or (not 0 <= ny < Y):
                return True, moats
            elif d[ny][nx] == float('inf'):
                if field[ny][nx] == '#':
                    moats.add((nx, ny))
                else:
                    Q.append((nx, ny))
                    d[ny][nx] = d[cy][cx] + 1
    return False, moats


def fill_moat(field, moats):
    # ??¢??\???????????¨????????????????????£??????????????????'^'??§?????????
    dy = [-1, 1, 0, 0]
    dx = [0, 0, -1, 1]
    # ??°???????????????(?§????????????£????????????????????????????????§??????????????¨)
    Y = len(field)
    X = len(field[0])
    d = [[float('inf')] * X for _ in range(Y)] #  ??????????????°?????????????????¢???INF??§?????????

    while moats:
        cx, cy = moats.pop()        #  ?????¨??°?????§?¨?
        field[cy][cx] = '^'
        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]
            if (0 <= nx < X) and (0 <= ny < Y) and d[ny][nx] == float('inf'):
                if field[ny][nx] == '#':
                    moats.add((nx, ny))
                    d[ny][nx] = d[cy][cx] + 1


def solve(field):
    # ??????????????°???(S)??¨??´????????°???(N)?????????
    start = (0, 0)
    for y, row in enumerate(field):
        if '&' in row:
            start = (row.index('&'), y)

    sx, sy = start
    climb = 0
    while True:
        res, moats = bfs(field, sx, sy)
        if res is False:
            climb += 1
            fill_moat(field, moats)
        else:
            break
    return climb


def main(args):
    while True:
        n, m = map(int, input().split())
        if n == 0 and m == 0:
            break

#        data = [
#         '.###.',
#         '#...#',
#         '#.&.#',
#         '#...#',
#         '.###.'
#        ]

        data = [input().strip('\n') for _ in range(m)]
        field = [list(x) for x in data] #  data????????????????????????????????????????????????
        result = solve(field)
        print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0156

"""
import sys
from sys import stdin
from collections import deque
input = stdin.readline


def bfs(field, sx, sy):
    """
    ??????????????°???????????°??????????????§??????????????????
    :param field:
    :param sx: ??????????????°????????§?¨?
    :param sy:
    :return: ????????????????????´???????????§????????¢
    """
    # ????????????????§????????????´????????§?¨?????????????
    dy = [-1, 1, 0, 0]
    dx = [0, 0, -1, 1]
    # ??°???????????????(?§????????????£????????????????????????????????§??????????????¨)
    Y = len(field)
    X = len(field[0])
    d = [[float('inf')] * X for _ in range(Y)] #  ??????????????°?????????????????¢???INF??§?????????
    moats = set()                   # ????????§???????????????????????§?¨?

    # ???????????????????????????????????°???????????´????????°????????§????????¢????±???????
    Q = deque()
    Q.append((sx, sy))
    d[sy][sx] = 0               #  ??????????????°??????????????????0
    while Q:
        cx, cy = Q.popleft()        #  ?????¨??°?????§?¨?
        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]
            # ?§?????????? ??°????????????????????????????????? and ?£?????????£???????????? and ??¢?????¢?´¢?????§?????? ??´???
            if (not 0 <= nx < X) or (not 0 <= ny < Y):
                return True, moats
            elif d[ny][nx] == float('inf'):
                if field[ny][nx] == '#':
                    moats.add((nx, ny))
                else:
                    Q.append((nx, ny))
                    d[ny][nx] = d[cy][cx] + 1
    return False, moats


def fill_moat(field, moats):
    # ??¢??\???????????¨????????????????????£??????????????????'^'??§?????????
    dy = [-1, 1, 0, 0]
    dx = [0, 0, -1, 1]
    # ??°???????????????(?§????????????£????????????????????????????????§??????????????¨)
    Y = len(field)
    X = len(field[0])
    # d = [[float('inf')] * X for _ in range(Y)] #  ??????????????°?????????????????¢???INF??§?????????

    while moats:
        cx, cy = moats.pop()        #  ?????¨??°?????§?¨?
        field[cy][cx] = '^'
        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]
            if (0 <= nx < X) and (0 <= ny < Y):
                if field[ny][nx] == '#':
                    moats.add((nx, ny))
                    # d[ny][nx] = d[cy][cx] + 1


def solve(field):
    # ??????????????°???(????????£: &)?????????
    start = (0, 0)
    for y, row in enumerate(field):
        if '&' in row:
            start = (row.index('&'), y)

    sx, sy = start
    climb = 0                   #  ???????????????????????° = ??????????????????????????°
    while True:
        res, moats = bfs(field, sx, sy) #  ????????£????????°?????????????????????????¢????
        if res is False:
            climb += 1
            fill_moat(field, moats) #  ??¢??\?????????????????????
        else:
            break
    return climb


def main(args):
    while True:
        n, m = map(int, input().split())
        if n == 0 and m == 0:
            break

#        data = [
#         '.###.',
#         '#...#',
#         '#.&.#',
#         '#...#',
#         '.###.'
#        ]

        data = [input().strip('\n') for _ in range(m)]
        field = [list(x) for x in data] #  data????????????????????????????????????????????????
        result = solve(field)
        print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

while True:
  n, m = map(int, input().split())
  if n == 0: break

  mp = ["X" + input() + "X" for _ in range(m)]
  mp.insert(0, "X" * (n + 2))
  mp.append("X" * (n + 2))
  
  que = []
  visited = [[False] * (n + 2) for _ in range(m + 2)]
  sur_flag = False
  for i in range(1, n + 1):
    if mp[1][i] =="&" or mp[m][i] == "&":
      sur_flag = True
      break
    c1, s1 = (1, 0) if mp[1][i] == "#" else (0, 1)
    c2, s2 = (1, 0) if mp[m][i] == "#" else (0, 1)
    heappush(que, (c1, s1, (i, 1)))
    heappush(que, (c2, s2, (i, m)))
    visited[1][i] = True
    visited[m][i] = True
  
  for i in range(1, m + 1):
    if mp[i][1] == "&" or mp[i][n] == "&":
      sur_flag = True
      break
    c1, s1 = (1, 0) if mp[i][1] == "#" else (0, 1)
    c2, s2 = (1, 0) if mp[i][n] == "#" else (0, 1)
    heappush(que, (c1, s1, (1, i)))
    heappush(que, (c2, s2, (n, i)))
    visited[i][1] = True
    visited[i][n] = True
  
  if sur_flag:
    print(0)
    continue
  
  direct = ((0, 1), (0, -1), (1, 0), (-1, 0))
  reached = False
  
  while que and not reached:
    cost, status, point = heappop(que)
    x, y = point
    for dx, dy in direct:
      newx, newy = x + dx, y + dy
      if not visited[newy][newx]:
        visited[newy][newx] = True
        if mp[newy][newx] == "&":
          print(cost)
          reached = True
          break
        elif mp[newy][newx] == "#":
          if status == 1:
            heappush(que, (cost + 1, 0, (newx, newy)))
          else:
            heappush(que, (cost, 0, (newx, newy)))
        elif mp[newy][newx] == ".":
          heappush(que,(cost, 1, (newx, newy)))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

while True:
  n, m = map(int, input().split())
  if n == 0: break

  mp = ["X" + input() + "X" for _ in range(m)]
  mp.insert(0, "X" * (n + 2))
  mp.append("X" * (n + 2))
  
  que = []
  visited = [[False] * (n + 2) for _ in range(m + 2)]
  sur_flag = False
  for i in range(1, n + 1):
    if mp[1][i] =="&" or mp[m][i] == "&":
      sur_flag = True
      break
    c1, s1 = (1, 0) if mp[1][i] == "#" else (0, 1)
    c2, s2 = (1, 0) if mp[m][i] == "#" else (0, 1)
    heappush(que, (c1, s1, (i, 1)))
    heappush(que, (c2, s2, (i, m)))
    visited[1][i] = True
    visited[m][i] = True
  
  for i in range(1, m + 1):
    if mp[i][1] == "&" or mp[i][n] == "&":
      sur_flag = True
      break
    c1, s1 = (1, 0) if mp[i][1] == "#" else (0, 1)
    c2, s2 = (1, 0) if mp[i][n] == "#" else (0, 1)
    heappush(que, (c1, s1, (1, i)))
    heappush(que, (c2, s2, (n, i)))
    visited[i][1] = True
    visited[i][n] = True
  
  if sur_flag:
    print(0)
    continue
  
  direct = ((0, 1), (0, -1), (1, 0), (-1, 0))
  reached = False
  
  """
  到達コストの低い順で、堀の中にいるものを優先に幅優先探索
  """
  while que and not reached:
    cost, status, point = heappop(que)
    x, y = point
    for dx, dy in direct:
      newx, newy = x + dx, y + dy
      if not visited[newy][newx]:
        visited[newy][newx] = True
        sym = mp[newy][newx]
        if sym == "&":
          print(cost)
          reached = True
          break
        elif sym == "#":
          if status == 1:
            heappush(que, (cost + 1, 0, (newx, newy)))
          else:
            heappush(que, (cost, 0, (newx, newy)))
        elif sym == ".":
          heappush(que,(cost, 1, (newx, newy)))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from itertools import product

def solve():
    hq = [(0, y, x) for y, x in product(xrange(m), xrange(n)) 
          if not(0 < y < m - 1 and 0 < x < n - 1)]
    heapify(hq)
    while len(hq) != 0:
        cost, cy, cx = heappop(hq)
        if field[cy][cx] == "&":
            return cost
        if memo[cy][cx] <= cost:
            continue
        memo[cy][cx] = cost
        for dx, dy in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            ny, nx = cy + dy, cx + dx
            if 0 <= ny < m and 0 <= nx < n:
                if field[ny][nx] != "#" and field[cy][cx] == "#": 
                    heappush(hq, (cost + 1, ny, nx))
                else:
                    heappush(hq, (cost, ny, nx))
    return None

while True:
    n, m = map(int, raw_input().split())
    if n | m == 0:
        break
    memo = [[1 << 20] * n for _ in xrange(m)]
    field = [raw_input() for _ in xrange(m)]    
    print solve()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from itertools import product

def solve():
    hq = [(0, y, x) for y, x in product(xrange(m), xrange(n)) 
          if not(0 < y < m - 1 and 0 < x < n - 1)]
    heapify(hq)
    while len(hq) != 0:
        cost, cy, cx = heappop(hq)
        if field[cy][cx] == "&":
            return cost
        if memo[cy][cx] <= cost:
            continue
        memo[cy][cx] = cost
        for dx, dy in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            ny, nx = cy + dy, cx + dx
            if 0 <= ny < m and 0 <= nx < n:
                if field[ny][nx] != "#" and field[cy][cx] == "#": 
                    heappush(hq, (cost + 1, ny, nx))
                else:
                    heappush(hq, (cost, ny, nx))

while True:
    n, m = map(int, raw_input().split())
    if n | m == 0:
        break
    memo = [[1 << 20] * n for _ in xrange(m)]
    field = [raw_input() for _ in xrange(m)]    
    print solve()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from itertools import product

def solve():
    hq = [(0, y, x) for y, x in product(xrange(m), xrange(n)) 
          if not(0 < y < m - 1 and 0 < x < n - 1)]
    heapify(hq)
    while True:
        cost, cy, cx = heappop(hq)
        if field[cy][cx] == "&":
            return cost
        if memo[cy][cx] <= cost:
            continue
        memo[cy][cx] = cost
        for dx, dy in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            ny, nx = cy + dy, cx + dx
            if 0 <= ny < m and 0 <= nx < n:
                if field[ny][nx] != "#" and field[cy][cx] == "#": 
                    heappush(hq, (cost + 1, ny, nx))
                else:
                    heappush(hq, (cost, ny, nx))

while True:
    n, m = map(int, raw_input().split())
    if n | m == 0:
        break
    memo = [[1 << 20] * n for _ in xrange(m)]
    field = [raw_input() for _ in xrange(m)]    
    print solve()

Submission status: Accepted

Solution code:
from collections import deque

dd = ((-1, 0), (0, -1), (1, 0), (0, 1))

while 1:
    N, M = map(int, input().split())
    if N == M == 0:
        break
    MP = [input() for i in range(M)]
    cost = [[-1]*N for i in range(M)]
    cur = 0
    que = deque()
    for i in range(M):
        for j in range(N):
            if MP[i][j] == '&':
                que.append((i, j))
                cost[i][j] = 0

    while que:
        r, c = que.popleft()
        s = cost[r][c]
        a = MP[r][c]
        for dr, dc in dd:
            nr = r + dr; nc = c + dc
            if not 0 <= nr < M or not 0 <= nc < N or cost[nr][nc] != -1:
                continue
            b = MP[nr][nc]
            t = s + (a != '#' and b == '#')
            cost[nr][nc] = t
            if s == t:
                que.appendleft((nr, nc))
            else:
                que.append((nr, nc))

    ans = N*M
    for i in range(M):
        ans = min(ans, cost[i][0], cost[i][-1])
    for i in range(N):
        ans = min(ans, cost[0][i], cost[-1][i])
    print(ans)