A halfling is searching for treasure hidden in a maze in the dwarfs' mine. He has a map of the maze and would like to find the shortest path to the treasure.
The maze has a specific shape. It is placed on a square grid with M2 cells, where M = 2N+1+1 for some given size N. Each cell has coordinates (x, y), where 0 ≤ x, y < M, and can either be empty or contain a rock.
The mazes of sizes N = 1 and N = 2 are presented in the pictures below:
A maze of size N is constructed recursively from the layout of the maze of size N−1 (like the Hilbert curve). It contains four mazes of size N−1, each maze in one quarter. The maze in the bottom-left quarter is rotated by 90 degrees clockwise and the maze in the bottom-right quarter is rotated by 90 degrees counter-clockwise. The mazes in the top quarters are not rotated. There are three additional rocks (squares marked in green in the picture below) in the areas where the mazes intersect. The construction of the maze of size N = 3 is shown below:
The halfling would like to reach the treasure in the smallest number of steps possible. At each step, he can move to any one of the four adjacent cells (north, south, west, east) that does not contain a rock and is not outside of the grid.
For example, given N = 1, the halfling needs 8 steps to move from cell (2, 1) to cell (3, 4):
Write a function:
def solution(N, A, B, C, D)
that, given the size of the maze N, coordinates of the halfling (A, B) and coordinates of the treasure (C, D), returns the minimum number of steps required for the halfling to reach the treasure.
Examples
Given N = 1, A = 2, B = 1, C = 3 and D = 4 the function should return 8, as shown above.
Given N = 2, A = 2, B = 5, C = 6 and D = 6 the function should return 7:
Given N = 3, A = 6, B = 6, C = 10 and D = 13 the function should return 39:
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..25];
- A, B, C, D are integers within the range [0..2N+1];
- cells (A, B) and (C, D) do not contain rocks;
- the result will be an integer smaller than 2,147,483,647.
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
# -*- coding:utf-8 -*-
# &Author AnFany
# Lesson 91:Tasks from Indeed Prime 2016 challenge
# P 91.3 HilbertMaze
def judge_walkable(n, x, y):
"""
判断N=n的迷宫中,坐标为(x,y)的网格是否可以走过去,是的话0,否则返回1
超出迷宫边界的不在此处考虑,在函数point_go中判断
注意:题目中的迷宫最左上、左下角的网格坐标为(0, 2**(N+1)), (0, 0),本程序中分别定义为(0,0),(2**(N+1),0)
因此在寻找路径的时候,会对开始、结束的坐标也进行相应的转换
:param n: 迷宫的行、列数均为2**(N+1)+1
:param x: 网格的横坐标
:param y: 网格的纵坐标
:return: 判断此网格是否可以走过去,没有岩石说明就可以走过去
"""
# 需要将坐标(x,y)等价转换到N=1的迷宫中的网格。
# 此时给出N=1中的坐标的关系
maze_list = [[0, 0, 0, 0, 0], [0, 1, 1, 1, 0], [0, 1, 0, 1, 0], [0, 1, 0, 1, 0], [0, 0, 0, 0, 0]]
# N=1的迷宫中各个网格的情况
maze_dict = {(i, j): maze_list[i][j] for i in range(len(maze_list)) for j in range(len(maze_list[i]))}
while (x, y) not in maze_dict or n != 1:
# 首先判断处在小迷宫相交地方的三个网格
if x == 2 ** n:
if y == 1: # 左上,左下相交
return 1
elif y == 2 ** (n + 1) - 1: # 右上,右下相交
return 1
else:
return 0
if y == 2 ** n:
if x == 2 ** n - 1: # 左上,右上相交
return 1
else:
return 0
# 然后判断是否处于四周,
if x == 0 or x == 2 ** (n+1):
return 0
if y == 0 or y == 2 ** (n+1):
return 0
# 根据所在不同区域进行不同的变化
if 1 <= x < 2**n < y < 2**(n+1): # 右上
y -= 2**n # 向左平移2**n
elif 1 <= y < 2**n < x < 2**(n+1): # 左下
# 首先逆时针旋转90度, 原始的a行b列变为2**n-b行a列
a = x - 2 ** n
b = y
x, y = 2 ** n + 2 ** n-b, a
# 然后向上平移2**n个单位
x -= 2 ** n
elif 2**n < x < 2**(n+1)and 2**n < y < 2**(n+1): # 右下
# 首先顺时针旋转90度, 原始的a行b列变为b行(2**n-a)列
a = x - 2 ** n
b = y - 2 ** n
x, y = 2 ** n + b, 2**n + 2**n - a
# 然后向上平移2**n个单位
x -= 2 ** n
# 然后向左平移2**n个单位
y -= 2 ** n
n -= 1
return maze_dict[(x, y)]
def point_go(n, x, y):
"""
坐标为(x,y)的网格,在迷宫中可以去的坐标集合,上下左右不出迷宫边界,没有石块就可以抵达
:param n: 表示迷宫的大小
:param x: 网格的横坐标
:param y: 网格的纵坐标
:return: 可以去的坐标的集合
"""
point_list = []
length = 2 ** (n+1) + 1
# 上
if x >= 1:
if not judge_walkable(n, x-1, y):
point_list.append((x - 1, y))
# 下
if x < length - 1:
if not judge_walkable(n, x+1, y):
point_list.append((x + 1, y))
# 左
if y >= 1:
if not judge_walkable(n, x, y-1):
point_list.append((x, y - 1))
# 右
if y < length - 1:
if not judge_walkable(n, x, y+1):
point_list.append((x, y + 1))
return point_list
def manhattan(a, b, c, d):
"""
计算坐标为(a,b)的网格与坐标为(c,d)的网格之间的曼哈顿距离
曼哈顿距离:对应网格的横坐标差的绝对值与纵坐标的差的绝对值之和
:param a: 开始网格的横坐标
:param b: 开始网格的纵坐标
:param c: 结束网格的横坐标
:param d: 结束网格的纵坐标
:return: 曼哈顿距离
a,b = 2, 8
c,d = 6, 7
返回 |2-6| +|8-7| = 5
"""
return abs(a - c) + abs(b - d)
def solution(N, A, B, C, D):
"""
利用A*算法,返回迷宫中从起始点到结束点的最短路径的步数,
需要注意的是,题目中的网格坐标和数组中的网格坐标是相反的,现在按照数组为准
因此需要将题目中的起始点,和结束点的坐标进行转换。
时间复杂度为O(2**(2*N))
:param N: 定义迷宫大小
:param A: 起始点的X坐标
:param B: 起始点的Y坐标
:param C: 结束点的X坐标
:param D: 结束点的Y坐标
:return: 最短路径的步数
"""
if A == C and B == D:
return 0
# 真正的起始点、结束点的坐标
start_a, start_b = 2 ** (N + 1) - B, A
end_c, end_d = 2 ** (N + 1) - D, C
# 开始A*算法
close_list = {} # 已经走过的网格的集合,
open_list = {(start_a, start_b): [(start_a, start_b), 0]} # 将要走的网格的集合
while (end_c, end_d) not in open_list and open_list:
# 选择open_list里面代价函数最小的网格
cost_least = min(open_list.items(), key=lambda k: k[1][1])[0]
# 计算可以去的相邻的网格
x, y = cost_least
point_list = point_go(N, x, y)
copy_open_list = open_list.copy()
if point_list:
for j in point_list:
if j in close_list: # 忽略
pass
elif j in open_list: # 需要对比值,选择较小的,并且更改父亲的节点
new_cost = 1 + manhattan(j[0], j[1], end_c, end_d)
if new_cost < open_list[j][1]:
copy_open_list[j][0] = cost_least
else:
copy_open_list[j] = [(x, y), 1 + manhattan(j[0], j[1], end_c, end_d) + open_list[(x, y)][1]]
# 存储到已经走过的网格中
close_list[cost_least] = open_list[cost_least][0]
del copy_open_list[cost_least]
open_list = copy_open_list
if not open_list: # 无解
return 0
else: # 获得最佳的路径
close_list[(end_c, end_d)] = open_list[(end_c, end_d)][0]
end_sign = 0
path_list = [(end_c, end_d)]
while end_sign != (start_a, start_b):
end_sign = close_list[path_list[-1]]
path_list.append(end_sign)
# 为了使得坐标和迷宫是一样的,现在进行转换,主要是为了验证结果的正确性
trans_list = []
for h in path_list:
trans_list.append([h[1], 2 ** (N+1) - h[0]])
return len(trans_list) - 1
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
# -*- coding:utf-8 -*-
# &Author AnFany
# Lesson 91:Tasks from Indeed Prime 2016 challenge
# P 91.3 HilbertMaze
def judge_walkable(n, x, y):
"""
判断N=n的迷宫中,坐标为(x,y)的网格是否可以走过去,是的话0,否则返回1
超出迷宫边界的不在此处考虑,在函数point_go中判断
注意:题目中的迷宫最左上、左下角的网格坐标为(0, 2**(N+1)), (0, 0),本程序中分别定义为(0,0),(2**(N+1),0)
因此在寻找路径的时候,会对开始、结束的坐标也进行相应的转换
:param n: 迷宫的行、列数均为2**(N+1)+1
:param x: 网格的横坐标
:param y: 网格的纵坐标
:return: 判断此网格是否可以走过去,没有岩石说明就可以走过去
"""
# 需要将坐标(x,y)等价转换到N=1的迷宫中的网格。
# 此时给出N=1中的坐标的关系
maze_list = [[0, 0, 0, 0, 0], [0, 1, 1, 1, 0], [0, 1, 0, 1, 0], [0, 1, 0, 1, 0], [0, 0, 0, 0, 0]]
# N=1的迷宫中各个网格的情况
maze_dict = {(i, j): maze_list[i][j] for i in range(len(maze_list)) for j in range(len(maze_list[i]))}
while (x, y) not in maze_dict or n != 1:
# 首先判断处在小迷宫相交地方的三个网格
if x == 2 ** n:
if y == 1: # 左上,左下相交
return 1
elif y == 2 ** (n + 1) - 1: # 右上,右下相交
return 1
else:
return 0
if y == 2 ** n:
if x == 2 ** n - 1: # 左上,右上相交
return 1
else:
return 0
# 然后判断是否处于四周,
if x == 0 or x == 2 ** (n+1):
return 0
if y == 0 or y == 2 ** (n+1):
return 0
# 根据所在不同区域进行不同的变化
if 1 <= x < 2**n < y < 2**(n+1): # 右上
y -= 2**n # 向左平移2**n
elif 1 <= y < 2**n < x < 2**(n+1): # 左下
# 首先逆时针旋转90度, 原始的a行b列变为2**n-b行a列
a = x - 2 ** n
b = y
x, y = 2 ** n + 2 ** n-b, a
# 然后向上平移2**n个单位
x -= 2 ** n
elif 2**n < x < 2**(n+1)and 2**n < y < 2**(n+1): # 右下
# 首先顺时针旋转90度, 原始的a行b列变为b行(2**n-a)列
a = x - 2 ** n
b = y - 2 ** n
x, y = 2 ** n + b, 2**n + 2**n - a
# 然后向上平移2**n个单位
x -= 2 ** n
# 然后向左平移2**n个单位
y -= 2 ** n
n -= 1
return maze_dict[(x, y)]
def point_go(n, x, y):
"""
坐标为(x,y)的网格,在迷宫中可以去的坐标集合,上下左右不出迷宫边界,没有石块就可以抵达
:param n: 表示迷宫的大小
:param x: 网格的横坐标
:param y: 网格的纵坐标
:return: 可以去的坐标的集合
"""
point_list = []
length = 2 ** (n+1) + 1
# 上
if x >= 1:
if not judge_walkable(n, x-1, y):
point_list.append((x - 1, y))
# 下
if x < length - 1:
if not judge_walkable(n, x+1, y):
point_list.append((x + 1, y))
# 左
if y >= 1:
if not judge_walkable(n, x, y-1):
point_list.append((x, y - 1))
# 右
if y < length - 1:
if not judge_walkable(n, x, y+1):
point_list.append((x, y + 1))
return point_list
def manhattan(a, b, c, d):
"""
计算坐标为(a,b)的网格与坐标为(c,d)的网格之间的曼哈顿距离
曼哈顿距离:对应网格的横坐标差的绝对值与纵坐标的差的绝对值之和
:param a: 开始网格的横坐标
:param b: 开始网格的纵坐标
:param c: 结束网格的横坐标
:param d: 结束网格的纵坐标
:return: 曼哈顿距离
a,b = 2, 8
c,d = 6, 7
返回 |2-6| +|8-7| = 5
"""
return abs(a - c) + abs(b - d)
def solution(N, A, B, C, D):
"""
利用A*算法,返回迷宫中从起始点到结束点的最短路径的步数,
需要注意的是,题目中的网格坐标和数组中的网格坐标是相反的,现在按照数组为准
因此需要将题目中的起始点,和结束点的坐标进行转换。
时间复杂度为O(2**(2*N))
:param N: 定义迷宫大小
:param A: 起始点的X坐标
:param B: 起始点的Y坐标
:param C: 结束点的X坐标
:param D: 结束点的Y坐标
:return: 最短路径的步数
"""
if A == C and B == D:
return 0
# 真正的起始点、结束点的坐标
start_a, start_b = 2 ** (N + 1) - B, A
end_c, end_d = 2 ** (N + 1) - D, C
# 开始A*算法
close_list = {} # 已经走过的网格的集合,
open_list = {(start_a, start_b): [(start_a, start_b), 0]} # 将要走的网格的集合
while (end_c, end_d) not in open_list and open_list:
# 选择open_list里面代价函数最小的网格
cost_least = min(open_list.items(), key=lambda k: k[1][1])[0]
# 计算可以去的相邻的网格
x, y = cost_least
point_list = point_go(N, x, y)
copy_open_list = open_list.copy()
if point_list:
for j in point_list:
if j in close_list: # 忽略
pass
elif j in open_list: # 需要对比值,选择较小的,并且更改父亲的节点
new_cost = 1 + manhattan(j[0], j[1], end_c, end_d)
if new_cost < open_list[j][1]:
copy_open_list[j][0] = cost_least
else:
copy_open_list[j] = [(x, y), 1 + manhattan(j[0], j[1], end_c, end_d) + open_list[(x, y)][1]]
# 存储到已经走过的网格中
close_list[cost_least] = open_list[cost_least][0]
del copy_open_list[cost_least]
open_list = copy_open_list
if not open_list: # 无解
return 0
else: # 获得最佳的路径
close_list[(end_c, end_d)] = open_list[(end_c, end_d)][0]
end_sign = 0
path_list = [(end_c, end_d)]
while end_sign != (start_a, start_b):
end_sign = close_list[path_list[-1]]
path_list.append(end_sign)
# 为了使得坐标和迷宫是一样的,现在进行转换,主要是为了验证结果的正确性
trans_list = []
for h in path_list:
trans_list.append([h[1], 2 ** (N+1) - h[0]])
return len(trans_list) - 1
The following issues have been detected: timeout errors.
For example, for the input (8, 10, 384, 304, 18) the solution exceeded the time limit.
small tests with long path, N <= 8
running time: >3.00 sec., time limit: 2.00 sec.
large tests, random cells, N ~= 25
running time: >2.00 sec., time limit: 0.16 sec.
large tests with long path, N ~= 25
running time: >2.00 sec., time limit: 0.16 sec.
large tests with short path, N ~= 25
running time: >2.00 sec., time limit: 0.16 sec.
large tests, random cells, N ~= 25
running time: >2.00 sec., time limit: 0.16 sec.
large tests, random cells, N ~= 25
running time: >2.00 sec., time limit: 0.16 sec.
large tests, random cells, N ~= 25
running time: >2.00 sec., time limit: 0.16 sec.