运用广度优先搜素

解题思路:通过队列，运用广度优先搜索

注意事项:在pycharm上这个代码会报错，但是提交以后是 正确的

参考代码:

from collections import deque


def dfs(gra):
   x1, y1 = index(gra,"@")
   x2, y2 = index(gra,"*")
   dx = [1, 0, -1, 0]
   dy = [0, 1, 0, -1]
   visited = [[False for _ in range(n)] for _ in range(m)]
   visited[x1][y1] = True
   queue = deque()
   queue.append((x1, y1, 0))
   while queue:
       curNode = queue.popleft()
       if curNode[0] == x2 and curNode[1] == y2:
           return curNode[2]

       for i in range(4):
           tx = curNode[0] + dx[i]
           ty = curNode[1] + dy[i]

           if 0 <= tx < m and 0 <= ty < n :
               if (gra[tx][ty] == "." or gra[tx][ty] == "*") and not visited[tx][ty]:
                   visited[tx][ty] = True
                   queue.append((tx, ty, curNode[2] + 1))
   return -1


def index(num,tar):
   for i in range(len(num)):
       for j in range(len(num[0])):
           if num[i][j] == tar:
               return i,j

while True:
   m, n = map(int, input().split())
   if m == 0 and n == 0:
       break
   gra = []
   for i in range(m):
       data = list(input())
       gra.append(data)
   print(dfs(gra))