如何检查指针是否可以在给定固定移动次数的情况下遍历可能的路径
How to check if a pointer can traverse a possible path given a fixed number of moves
我正在尝试在 Hackerrank 上解决这个问题：
我有这个输入：
........#....#..#..#....#...#..#.#.#.#.#.#..#.....
..#..#..#.#....#..#.....#......#..##...........##.
.........#.###.##...#.....##......###............#
....##........#..#.#.#......#...#.##.......##.....
.................###...#.#...#......#.#.#.#.#...#.
.........#.....#...........##....#.#.#.##.....##..
.....#.##............#....#......#..#..#...##.....
.#.......###....#.#..##.##.#...##...#........#...#
..#.##..##..........#..........##.....##..........
#.#..##......#.#.#..##.###...#.........###..#...#.
.#..#..............#...#........#..#...#....#..#..
##..#..#........#....#........#...#.#......#.....#
#.#.......#.#..#...###..#..#.##...#.##.......#...#
#.#...#...#.....#....#......##.#.#.........#....#.
.#..........#......##..#....#....#.#.#..#..###....
#.#............#.##..#.##.##......###......#..#..#
.#..#.##...#.#......................#........#....
.....#....#.#..........##.#.#................#....
##............#.#......####...#.........#..##..#..
....#..##..##...#.........##..##....#..#.##...#...
.#........#...#..#...........#.###.....##.....##..
.......#..#..##...#..###.....#..##.........#......
...#......#..#...........###...............#......
...##.###.#.#....#...#..#.#.#....#....#.##.#...#..
..........#.......#..#..#...###....##.....#..#....
.............##.##.#.......#.#....#.......#..#..#.
.......#........#.....#....##...#...#.#...#.#.##..
.....#..#..#........#..#.....#...#.##.#....#...#..
....................#.#...#....###...###...##...#.
##.#.....##.....#..#.#.#...........#.#.##...#..#.#
#...........#....#.##...#.#.....#...#.....#.#.....
..#..##...#........#.##..#.....##.......#...#.#.#.
......#....#...##...........#..#.......#.##.......
......#..#..#.###..........#...#...........#..#...
....#.#..#..#.#.#...#.......#...#.##......#.......
....#.......#..#........#...#.#...#......#.......#
.#....##...#.#..#....#.#.##........#..#.#.........
#....#.......#..##......##...............#..#.##..
...#..##.......#.....#....#...#.#......#..##..###.
.....#...#...#...#...#...#..##...#..#.............
....##......#...#..#...#...#.#....#.....#..#.##...
...##.......#..##.....#........#.#....#...#.......
..#...#....#...#.###......#................#......
...#...###...#..##...###.....................#....
.....#....#....#...#.#.#.##....##......#....##....
...#.###...##.........#..........#.##.#.....#.....
##..#...#.........#.......#......##...........####
...###.#..........#.....#####........#..#.#.#...#.
...#..#.....#..##.##.#.....##...#...#.#.....#...##
.##.......#.##....#............#..................
#.....#.........#.#.........#..###....##...##.....
#....#.....#...#.....#.##...##...####........#....
#...........#..#...#........#.##..##..#...#.#.....
..#.#................#......###..##.#.#...##...#..
.#.#....#..#............#....#......#............#
..#..#...#.#.#...#...........#.......##.#...#.#...
#..........#.....#.....#......#.......#.#...##....
.......#...........#...........#....#............#
...####.#.....#.##.....#.......##.#..#......#.....
.#..#.....#..#......#.............#.#.#..##...#...
..#.#.#.........#...#..#.......#................##
.#..##.#.#...#.............#..#..........#..#...#.
....#........#......#...###..#.#..................
#..#..#.....#.#.#...##....##........#........#....
.....#.#.......##.......#.....#........#..##..#...
#.#.##........#..##.#..#.#...#........#.#......#..
....#.#.#.......#.##.##...##...#..#.###...#.#.#...
.....##.#....#........#....#.#........#.#.#.....#.
.....#..##..#.#....#.......#...#.#.###.........#.#
#.....#.##..#.......###.........#..##..#......##..
70 行，最大时间为 2244
这是我的策略，但它适用于某些测试用例：
import math
import collections
def reachTheEnd(grid, maxTime):
# Write your code here
grid = [i for i in grid]
yes = 'Yes'
no = 'No'
counter = 0
for i in grid:
counter += i.count('.')
if maxTime <= counter:
return yes
elif i != i[::-1]:
return no
else:
return no
print(counter)
这是一个 BFS 问题，但我无法弄清楚其中的逻辑。感谢您的帮助。
广度优先搜索的思想是您 (1) 不会访问同一个节点两次，并且 (2) 不断维护一个您未访问过的节点列表，按时间片划分。最终，您访问了所有可访问的节点，并且对于您访问的任何节点，您都以尽可能少的步骤访问它。
在下面的算法中，我们创建一个缓存来满足（1）和一个队列来满足（2）。每个时间片，我们检查队列的每个元素，并用一个新队列完全替换队列，该队列由在该时间片中发现的元素组成。每当我们发现一个新元素时，我们都会将它连同首次发现它的时间片一起添加到缓存中 - 那么，这一定是到达该新元素的最快路径。
如果我们在到达目的地之前 运行 没有时间或 运行 没有新的单元格可供探索，那么我们就失败了。否则，我们就成功了。我们可以通过简单地编码我们的退出条件并检查我们是否在退出 while 循环时访问了目的地来检查。
def reachTheEnd(grid, maxTime):
# mark what the coordinates of the destination are
destination = (len(grid) - 1, len(grid[-1]) - 1)
# initialize
# - a step counter
# - a cache of visited cells on the grid
# - a queue of not-yet-visited cells that are adjacent to visited cells
counter = 0
cache = {(0, 0): 0}
queue = [(0, 0)]
# perform breadth-first search on the current queue, moving forward one
# timeslice. On each timeslice, we take one 'step' forward in any direction
# towards a newly-accessible tile on the grid.
# our 'exit' conditions are
# - we run out of time
# - there is no path to the end of the maze
# - we reach the end
while counter < maxTime and len(queue) > 0 and destination not in cache:
counter += 1
new_queue = []
for (x, y) in queue:
# check adding to path in all directions (up, down, left, right)
# If the step is
# - not out-of-bounds
# - not a wall
# - not already visited
# then add it to the cache with the current step count, as this is
# is the most quickly we can reach it. Also add it to the queue of
# cells to investigate on the next timeslice.
for (dx, dy) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
(nx, ny) = (x + dx, y + dy)
if 0 <= nx < len(grid) \
and 0 <= ny < len(grid[nx]) \
and grid[nx][ny] == '.' \
and (nx, ny) not in cache:
cache[(nx, ny)] = counter
new_queue.append((nx, ny))
queue = new_queue
# by the time the loop exits, either we've failed to reach the end,
# or the end is in the cache with the quickest possible path to it.
if destination in cache:
return "Yes"
else:
return "No"
一个可能的优化是将“我们到达目的地了吗”移动到最里面的 for 循环内，这将节省处理该时间片上的其余队列。但是，这会使代码稍微复杂一些（因此对于解释 BFS 的概念用处不大）并且只能节省最少的时间。
请注意，对于您提供的 70x50 大网格，无法真正到达右下角的方块（它是一个被墙包围的小岛）。它可以通过时间片 117 到达单元格 (67, 49)，这是最接近的，但不能绕过墙。
我正在尝试在 Hackerrank 上解决这个问题：
我有这个输入：
........#....#..#..#....#...#..#.#.#.#.#.#..#.....
..#..#..#.#....#..#.....#......#..##...........##.
.........#.###.##...#.....##......###............#
....##........#..#.#.#......#...#.##.......##.....
.................###...#.#...#......#.#.#.#.#...#.
.........#.....#...........##....#.#.#.##.....##..
.....#.##............#....#......#..#..#...##.....
.#.......###....#.#..##.##.#...##...#........#...#
..#.##..##..........#..........##.....##..........
#.#..##......#.#.#..##.###...#.........###..#...#.
.#..#..............#...#........#..#...#....#..#..
##..#..#........#....#........#...#.#......#.....#
#.#.......#.#..#...###..#..#.##...#.##.......#...#
#.#...#...#.....#....#......##.#.#.........#....#.
.#..........#......##..#....#....#.#.#..#..###....
#.#............#.##..#.##.##......###......#..#..#
.#..#.##...#.#......................#........#....
.....#....#.#..........##.#.#................#....
##............#.#......####...#.........#..##..#..
....#..##..##...#.........##..##....#..#.##...#...
.#........#...#..#...........#.###.....##.....##..
.......#..#..##...#..###.....#..##.........#......
...#......#..#...........###...............#......
...##.###.#.#....#...#..#.#.#....#....#.##.#...#..
..........#.......#..#..#...###....##.....#..#....
.............##.##.#.......#.#....#.......#..#..#.
.......#........#.....#....##...#...#.#...#.#.##..
.....#..#..#........#..#.....#...#.##.#....#...#..
....................#.#...#....###...###...##...#.
##.#.....##.....#..#.#.#...........#.#.##...#..#.#
#...........#....#.##...#.#.....#...#.....#.#.....
..#..##...#........#.##..#.....##.......#...#.#.#.
......#....#...##...........#..#.......#.##.......
......#..#..#.###..........#...#...........#..#...
....#.#..#..#.#.#...#.......#...#.##......#.......
....#.......#..#........#...#.#...#......#.......#
.#....##...#.#..#....#.#.##........#..#.#.........
#....#.......#..##......##...............#..#.##..
...#..##.......#.....#....#...#.#......#..##..###.
.....#...#...#...#...#...#..##...#..#.............
....##......#...#..#...#...#.#....#.....#..#.##...
...##.......#..##.....#........#.#....#...#.......
..#...#....#...#.###......#................#......
...#...###...#..##...###.....................#....
.....#....#....#...#.#.#.##....##......#....##....
...#.###...##.........#..........#.##.#.....#.....
##..#...#.........#.......#......##...........####
...###.#..........#.....#####........#..#.#.#...#.
...#..#.....#..##.##.#.....##...#...#.#.....#...##
.##.......#.##....#............#..................
#.....#.........#.#.........#..###....##...##.....
#....#.....#...#.....#.##...##...####........#....
#...........#..#...#........#.##..##..#...#.#.....
..#.#................#......###..##.#.#...##...#..
.#.#....#..#............#....#......#............#
..#..#...#.#.#...#...........#.......##.#...#.#...
#..........#.....#.....#......#.......#.#...##....
.......#...........#...........#....#............#
...####.#.....#.##.....#.......##.#..#......#.....
.#..#.....#..#......#.............#.#.#..##...#...
..#.#.#.........#...#..#.......#................##
.#..##.#.#...#.............#..#..........#..#...#.
....#........#......#...###..#.#..................
#..#..#.....#.#.#...##....##........#........#....
.....#.#.......##.......#.....#........#..##..#...
#.#.##........#..##.#..#.#...#........#.#......#..
....#.#.#.......#.##.##...##...#..#.###...#.#.#...
.....##.#....#........#....#.#........#.#.#.....#.
.....#..##..#.#....#.......#...#.#.###.........#.#
#.....#.##..#.......###.........#..##..#......##..
70 行，最大时间为 2244
这是我的策略，但它适用于某些测试用例：
import math
import collections
def reachTheEnd(grid, maxTime):
# Write your code here
grid = [i for i in grid]
yes = 'Yes'
no = 'No'
counter = 0
for i in grid:
counter += i.count('.')
if maxTime <= counter:
return yes
elif i != i[::-1]:
return no
else:
return no
print(counter)
这是一个 BFS 问题，但我无法弄清楚其中的逻辑。感谢您的帮助。
广度优先搜索的思想是您 (1) 不会访问同一个节点两次，并且 (2) 不断维护一个您未访问过的节点列表，按时间片划分。最终，您访问了所有可访问的节点，并且对于您访问的任何节点，您都以尽可能少的步骤访问它。
在下面的算法中，我们创建一个缓存来满足（1）和一个队列来满足（2）。每个时间片，我们检查队列的每个元素，并用一个新队列完全替换队列，该队列由在该时间片中发现的元素组成。每当我们发现一个新元素时，我们都会将它连同首次发现它的时间片一起添加到缓存中 - 那么，这一定是到达该新元素的最快路径。
如果我们在到达目的地之前 运行 没有时间或 运行 没有新的单元格可供探索，那么我们就失败了。否则，我们就成功了。我们可以通过简单地编码我们的退出条件并检查我们是否在退出 while 循环时访问了目的地来检查。
def reachTheEnd(grid, maxTime):
# mark what the coordinates of the destination are
destination = (len(grid) - 1, len(grid[-1]) - 1)
# initialize
# - a step counter
# - a cache of visited cells on the grid
# - a queue of not-yet-visited cells that are adjacent to visited cells
counter = 0
cache = {(0, 0): 0}
queue = [(0, 0)]
# perform breadth-first search on the current queue, moving forward one
# timeslice. On each timeslice, we take one 'step' forward in any direction
# towards a newly-accessible tile on the grid.
# our 'exit' conditions are
# - we run out of time
# - there is no path to the end of the maze
# - we reach the end
while counter < maxTime and len(queue) > 0 and destination not in cache:
counter += 1
new_queue = []
for (x, y) in queue:
# check adding to path in all directions (up, down, left, right)
# If the step is
# - not out-of-bounds
# - not a wall
# - not already visited
# then add it to the cache with the current step count, as this is
# is the most quickly we can reach it. Also add it to the queue of
# cells to investigate on the next timeslice.
for (dx, dy) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
(nx, ny) = (x + dx, y + dy)
if 0 <= nx < len(grid) \
and 0 <= ny < len(grid[nx]) \
and grid[nx][ny] == '.' \
and (nx, ny) not in cache:
cache[(nx, ny)] = counter
new_queue.append((nx, ny))
queue = new_queue
# by the time the loop exits, either we've failed to reach the end,
# or the end is in the cache with the quickest possible path to it.
if destination in cache:
return "Yes"
else:
return "No"
一个可能的优化是将“我们到达目的地了吗”移动到最里面的 for 循环内，这将节省处理该时间片上的其余队列。但是，这会使代码稍微复杂一些（因此对于解释 BFS 的概念用处不大）并且只能节省最少的时间。
请注意，对于您提供的 70x50 大网格，无法真正到达右下角的方块（它是一个被墙包围的小岛）。它可以通过时间片 117 到达单元格 (67, 49)，这是最接近的，但不能绕过墙。