博客论坛网站开发/电商运营是做什么的

1. 问题描述：

给定一个 n×n 的方格矩阵，行、列编号为 1∼n，其中第 i 行第 j 列的方格坐标为 (i，j)。每个方格要么是平地，要么是陷阱。旅行者从方格 (r1，c1) 出发，要前往方格 (r2，c2) 处。出发点和目的地保证都是平地。旅行者每次移动可以沿上、下、左、右四个方向，移动一格距离。移动过程中，不得走出矩阵或进入陷阱。由于存在陷阱的原因，旅行者可能无法顺利抵达目的地。幸运的是，他可以任意选择两个平地方格，在上面建立一对传送阵。传送阵能够支持旅行者在两个平地方格之间自由传送。但是，建立传送阵是一笔不容小视的花费。在方格 (rs，cs) 和 (rt，ct) 处建立传送阵，所需成本为 (rs − rt) * 2 + (cs − ct) * 2。请你计算，为了使旅行者能够成功抵达目的地，建立传送阵所需花费的最低成本。如果旅行者可以无需建立传送阵，直接走到目的地，那么成本就是 0。注意，最多只能建立一对传送阵。

输入格式

第一行包含整数 n，表示矩阵尺寸。第二行包含两个整数 r1，c1，表示起点方格坐标为 (r1，c1)。第三行包含两个整数 r2，c2，表示目的地方格坐标为 (r2，c2)。接下来 n 行，每行包含一个长度为 n 的 01 字符串，其中第 i 行第 j 个字符如果为 0，则表示方格 (i，j) 是平地，如果为 1，则表示方格 (i，j) 是陷阱。

输出格式

输出一个整数，表示为了确保旅行能够成功，所需花费的最小成本。

数据范围

前三个测试点满足，1 ≤ n ≤ 10。
所有测试点满足，1 ≤ n ≤ 50，1 ≤ r1，c1，r2，c2 ≤ n。

输入样例1：

5
1 1
5 5
00001
11111
00111
00110
00110

输出样例1：

10

输入样例2：

3
1 3
3 1
010
101
010

输出样例2：

8

输入样例3：

1
1 1
1 1
0

输出样例3：

0
来源：https://www.acwing.com/problem/content/description/4007/

2. 思路分析：

因为矩阵最大为50 * 50，所以需要将时间复杂度控制在O(n ^ 2)以内，首先如果起点可以到达终点那么成本就是0，如果不能够到达终点说明起点与终点之间需要建立传送带，所以我们可以预处理一下所有起点能够到达的点，终点可以到达的点，我们可以在这些格子建立连接，所有与起点相连的点都可以作为入口，所有与终点相连的点都可以最为出口，所以只需要枚举一下入口与出口对应的点对更新最小值即可

3. 代码如下：

from typing import List
import sysclass Solution:# 右左上下四个方向pos = [[0, 1], [0, -1], [-1, 0], [1, 0]]# 搜索x, y可以到达的所有位置def dfs(self, x: int, y: int, n: int, st: List[List[int]], g: List[List[str]]):st[x][y] = 1for i in range(4):a, b = x + self.pos[i][0], y + self.pos[i][1]# 判断当前是否可以往下搜索if 0 <= a < n and 0 <= b < n and g[a][b] == "0" and st[a][b] == 0:self.dfs(a, b, n, st, g)def process(self):n = int(input())sx, sy = map(int, input().split())tx, ty = map(int, input().split())# 输入的坐标是从1开始的所以需要减1转化为下标从0开始sx -= 1sy -= 1tx -= 1ty -= 1g = list()for i in range(n):g.append(list(input()))st1, st2 = [[0] * (n + 10) for i in range(n + 10)], [[0] * (n + 10) for i in range(n + 10)]self.dfs(sx, sy, n, st1, g)if st1[tx][ty] == 1:return 0else:# 说明起点与终点不连通需要从终点开始搜可以到达的位置, 然后暴力枚举self.dfs(tx, ty, n, st2, g)res = 10 ** 8for i in range(n):for j in range(n):if st1[i][j] == 1:for x in range(n):for y in range(n):if st2[x][y] == 1:res = min(res, (i - x) * (i - x) + (j - y) * (j - y))return resif __name__ == '__main__':# 因为最多有2500个数据超过了python递归次数为1000左右的最大限制需要设置一下递归调用的最大次数sys.setrecursionlimit(2500)print(Solution().process())