## 题目描述：

John is standing at the origin of an infinite two-dimensional grid. He is going to move along this grid. During each second he can either stay where he is or he can move by one unit in one of the four cardinal directions (north, south, east, or west). Some of the grid points are blocked. John is not allowed to move to a blocked grid point.

You are given the coordinates of the blocked grid points as tuple (integer)s x and y. For each valid i, the grid point that is x[i] units east and y[i] units north of the origin is blocked. You are also given an integer k. Compute and return the maximal possible x-coordinate of a point John can reach in k seconds.

Constraints
- x will contain between 0 and 47 elements, inclusive.
- x and y will contain the same number of elements.
- Each element of x will be between -1,000 and 1,000, inclusive.
- Each element of y will be between -1,000 and 1,000, inclusive.
- All pairs (x[i], y[i]) will be distinct.
- Each pair (x[i], y[i]) will be different from (0, 0).
- k will be between 1 and 1,000, inclusive.

## 题目大意：

John站在无限二维坐标网格的原点(0,0)。他沿着网格行走，每秒任选坐标系4个方向（东、南、西、北）之一移动1个单位。网格中的一些点禁止通行。

## 解题思路：

x轴极限情况：

障碍物由原点出发，上下包围x轴向左延伸至-47 / 2处，y坐标为±1。

y轴极限情况：

障碍物平行于y轴依次排列。

## Python代码：

``````class TheGridDivTwo:
def find(self, x, y, k):
HORIZON, MAX = 1024, 2048
dx = (1, -1, 0, 0)
dy = (0, 0, 1, -1)
visited = [[0] * MAX for i in range(MAX)] #visited[row][col]
size = len(x)
for i in range(size):
visited[x[i] + HORIZON][y[i] + HORIZON] = True
sp = (0, 0, k)
visited[sp[0]][sp[1]] = True
queue = [sp]
ans = 0
while queue: #BFS
point = queue.pop(0)
if point[2] == 0:
continue
for j in range(4):
np = (point[0] + dx[j], point[1] + dy[j], point[2] - 1)
if np[0] < -25 or np[1] > 25 or np[1] < -25: #Pruning
continue
if np[2] and np[0] + np[2] <= ans or visited[np[0] + HORIZON][np[1] + HORIZON]:
continue
visited[np[0] + HORIZON][np[1] + HORIZON] = True
queue.append(np)
ans = max(ans, np[0])
return ans
``````

Pingbacks已关闭。

1. Faris 发布于 2015年1月18日 10:35 #

话说这个python我还是很菜的～～～就是来打个酱油