Почему эта очередь BFS возвращает None? - PullRequest
Новая
       94

Почему эта очередь BFS возвращает None?

0 голосов
/ 20 сентября 2018

В настоящее время я пытаюсь решить проблему Hackerrank под названием Замок на сетке , в которой я реализовал BFS в Python 3 следующим образом: 

#!/bin/python3

import math
import os
import random
import re
import sys
from collections import deque

def minimumMoves(grid, startX, startY, goalX, goalY):
    n = len(grid)
    queue = deque()
    queue.append((startY,startX))
    goal = (goalY,goalX)
    turnsMatrix = [[0]*n]*n

    while queue:
        current = queue.popleft()
        (Y0, X0) = current
        print(current)
        d = turnsMatrix[Y0][X0]

        if current == goal:
            return(d)

        for X in range(X0-1,-1,-1):
            if grid[Y0][X] == 'X':
                break
            elif turnsMatrix[Y0][X] == 0:
                turnsMatrix[Y0][X] = d + 1
                queue.append((Y0,X))

        for Y in range(Y0-1,-1,-1):
            if grid[Y][X0] == 'X':
                break
            elif turnsMatrix[Y][X0] == 0:
                turnsMatrix[Y][X0] = d + 1
                queue.append((Y,X0))

        for X in range(X0+1,n):
            if grid[Y0][X] == 'X':
                break
            elif turnsMatrix[Y0][X] == 0:
                turnsMatrix[Y0][X] = d + 1
                queue.append((Y0,X))

        for Y in range(Y0+1,n):
            if grid[Y][X0] == 'X':
                break
            elif turnsMatrix[Y][X0] == 0:
                turnsMatrix[Y][X0] = d + 1
                queue.append((Y,X0))

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')
    n = int(input())
    grid = []

    for _ in range(n):
        grid_item = input()
        grid.append(grid_item)

    startXStartY = input().split()
    startX = int(startXStartY[0])
    startY = int(startXStartY[1])
    goalX = int(startXStartY[2])
    goalY = int(startXStartY[3])
    result = minimumMoves(grid, startX, startY, goalX, goalY)
    fptr.write(str(result) + '\n')
    fptr.close()

Однако, несмотря на только одно возвращениеоператор, который должен возвращать int d, мой код возвращает None.Я знаю, что deque в конечном итоге становится пустым и возвращает None, но мне трудно понять, почему вещи перестают добавляться в очередь.

Для контрольного примера 

3
.X.
.X.
...
0 0 0 2

Я заметил, что произойдет следующее:

1) замок движется вправо и ломается в точке X.

2) замок движется вниз на одну клетку, и матрица поворотов становится 

[[1, 0, 0], [1, 0, 0], [1, 0, 0]].

3) queue становится deque([(1, 0)]).

4) Ничего не возвращается.

Что происходит?Я несколько дней смотрю на свой код и схожу с ума ... пожалуйста, помогите, спасибо!

...