十字路口

[编程题]十字路口

热度指数：1583 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

在小美和小团生活的城市中，有n行m列共计n*m个十字路口，第i行j列的十字路口有两个属性a_ij，b_ij。当行人处在i行j列的路口，对于任意非负整数k:

当时间处在[k*a_ij+k*b_ij), (k+1)*a_ij+k*b_ij)时，行人可以选择走到i±1行j列的路口。

当时间处在[(k+1)*a_ij+k*b_ij), (k+1)*a_ij+(k+1)*b_ij)时，行人可以选择走到i行j±1列的路口。

每次移动花费的时间为1，且要保证将要去的十字路口存在，即属于n*m个路口当中。可以选择原地静止不动。

在第0时刻，小美处在x_s行y_s列的十字路口处，要去x_t行y_t列的十字路口找小团。小团原地不动等小美，请问小美所花费的时间最少是多少?

输入描述:

第一行六个正整数n，m，x_s，y_s，x_t，y_t，含义如上文所示。以样例第一行【5、5、2、4、4、3】共计6个数字为例，前两位数字代表有5*5的二维数组，三、四位数字代表小美处在2行4列的十字路口处，五、六位数字代表要去4行3列的十字路口找小团。

接下来n行每行m个正整数，在样例中为第一个5*5的二维数组，第i行第j个数代表i行j列十字路口的属性a_ij。

接下来n行每行m个正整数，在样例中为第二个5*5的二维数组，第i行第j个数代表i行j列十字路口的属性b_ij。

对于100%的数据，1≤n，m，x_s，y_s，x_t，y_t，a_ij，b_ij≤100。

输出描述:

输出1行1个整数代表答案。

示例1

输入

5 5 2 4 4 3
2 1 1 3 1
1 4 2 3 1
4 4 4 2 1
3 1 1 2 4
5 1 5 5 1
5 3 4 1 3
1 1 2 2 2
2 1 4 4 5
1 1 5 3 3
3 2 1 3 3

输出

算法知识视频讲解

Python

qingci

总结：一开始看到题很慌，感觉又是自己做不出的题了。但是还是没有放弃，试着用DP的思想理了下思路，逐步分析后发现越来越像类dij算法，这才灵感如泉涌，最终得出思路：

整体是广度优先搜索的策略，每次循环使用优先级队列pq维护的当前最近的点
并使用mat来记录已经遍历的结果，防止重复遍历。
加入剪枝优化，一旦出现需要的结果立刻跳出循环。

最终时间复杂度为nlogn量级，其中n为图中需遍历的点数，n小于等于 $10^4$

n, m, xs, ys, xt, yt = map(int, input().split())
a, b = [], []
for i in range(n):
 a.append(list(map(int, input().split())))
for i in range(n):
 b.append(list(map(int, input().split())))

# 准备工作
xt, yt = xt-1, yt-1
import heapq
pq = [(0, xs-1, ys-1)]
mat = [[-1]*m for i in range(n)]


# 用于计算对于当前时间当前十字路口那个方向可以通行，
# 同时返回去另一个方向需要等待的时间
def rule(t, i, j):
 ax, bx = a[i][j], b[i][j]
 t = t % (ax + bx)
 if t < ax:
     return True, ax - t
 else:
     return False, ax + bx - t



while pq:
 min_t, i, j = heapq.heappop(pq)
 if mat[i][j] != -1:
     continue
 mat[i][j] = min_t
 if i == xt and j == yt:
     ans = min_t
     break
 direc, t_w = rule(min_t, i, j)
 for step in [1, -1]:
     ni, nj = i + step, j + step
     if 0 <= nj < m:
         heapq.heappush(pq, (min_t + 1 + (t_w if direc else 0), i, nj))
     if 0 <= ni < n:
         heapq.heappush(pq, (min_t + 1 + (0 if direc else t_w), ni, j))
print(ans)

编辑于 2021-06-23 11:47:48 回复(0)