加米 lc490 求助迷宫题的边界条件细节讨论， python3，谢谢大家

大家好

题目lc490, the maze有一点边界条件细节上的疑问，请大家帮忙看看，会尽力加米。

题目 https://leetcode.com/problems/the-maze/
There is a ball in a maze with empty spaces (represented as 0) and walls (represented as 1). The ball can go through the empty spaces by rolling up, down, left or right, but it won't stop rolling until hitting a wall. When the ball stops, it could choose the next direction.
Given the m x n maze, the ball's start position and the destination, where start = [startrow, startcol] and destination = [destinationrow, destinationcol], return true if the ball can stop at the destination, otherwise return false.
You may assume that the borders of the maze are all walls (see examples).
example


Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [3,2]
Output: false
Explanation: There is no way for the ball to stop at the destination. Notice that you can pass through the destination but you cannot stop there.


看过discussion后我的思路：从startPosition开始，用BFS或者DFS遍历图，观察ball能否在destination停止。需要注意的是，本题中ball要滚到wall上才会停止；所以在向四个方向遍历时，只需要记录一直走到wall并且停止的stop position。本题中用while循环保证ball一直走到wall停止，维护一个set：stopped来记录遍历中停止的每一个stop_pos; 在每个stop_pos开始新的遍历（we only call the DFS from a stop position)；并把停止的stop_pos与destination相比。

我的疑问：
结束while循环后，找到newX,  newY是墙的坐标；我认为进入dfs()的坐标应该是[newX - i, newY -j]。https://leetcode.com/problems/th ... legant-DFS-solution

1. class Solution:
   
2.     def hasPath(self, maze, start, destination):
   
3.         m, n, stopped = len(maze), len(maze[0]), set()
   
4.         def dfs(x, y):
   
5.             if (x, y) in stopped:
   
6.                 return False
   
7.             stopped.add((x, y))
   
8.             if [x, y] == destination:
   
9.                 return True
   
10.             for i, j in (-1, 0) , (1, 0), (0, -1), (0, 1):
    
11.                 newX, newY = x, y
    
12.                 while 0 <= newX + i < m and 0 <= newY + j < n and maze[newX + i][newY + j] != 1:
    
13.                     newX += i
    
14.                     newY += j
    
15.                 if dfs(newX, newY):
    
16.                     return True
    
17.             return False
    
18.         return dfs(*start)

复制代码

1. 
   

复制代码

自己给自己回复吧哈哈哈，的确不需要减去i,j; 因为在condition里的坐标是[newX + i][newY + j]， newX, newY的终点不是墙。