2222. 迷宫

题意

摘要：终点为n,n，存在传送门，代价与走动代价相同，均为1，起点不定，求从初始格子走到终点的最短步数的期望值是多少
思路

两种写法，但都以BFS为基础
- 总体思路：要求求出所有点到终点的距离之和，所以我们反向思考，使用BFS以终点为起点跑遍整个地图,每次到一个新的位置时，此时到达的步数就是从终点到该点的最短步数，反过来也是从该点到终点的最短步数。为什么一定会是最短呢？因为BFS自带最短路效应。至于传送门采用二维坐标压缩至一维坐标，把坐标基准更改为[0, 0]，方便取余和整除
- 第一种：采用最短路策略，不用st数组，因为每个坐标可能走多次（当然在第一种思路中已经用st数组回避这个可能了），所以每次就得计算最短花费，dist初始化均为INF
- 第二种：以总体思路为标准，直接BFS，用到dist和st数组，其中dist数组其实可以省略（因其记录的是BFS层数，所以可以边遍历边加）

代码

第一种

# import
from sys import setrecursionlimit, stdin, stdout, exit
from collections import Counter, deque
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from bisect import bisect_left, bisect_right
from datetime import datetime, timedelta
from string import ascii_lowercase, ascii_uppercase
from math import log, gcd, sqrt, fabs, ceil, floorclass sa:def __init__(self, x, y):self.x = xself.y = ydef __lt__(self, a):return self.x < a.x# Final
N = int(2e3 + 10)
M = int(5e6 + 10)
INF = int(2e9)# Define
setrecursionlimit(INF)
input = lambda: stdin.readline().rstrip("\r\n")  # Remove when Mutiple data
read = lambda: map(int, input().split())
LTN = lambda x: ord(x.upper()) - 65  # A -> 0
NTL = lambda x: ascii_uppercase[x]  # 0 -> A# —————————————————————Division line ——————————————————————dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]g = [[] for _ in range(M)]
dist = [[INF] * N for _ in range(N)]def pos_to_num(x, y):x -= 1y -= 1return x * n + ydef num_to_pos(num):return [num // n + 1, num % n + 1]n, m = read()
for i in range(m):x1, y1, x2, y2 = read()g[pos_to_num(x1, y1)].append(pos_to_num(x2, y2))g[pos_to_num(x2, y2)].append(pos_to_num(x1, y1))def bfs(sx, sy):q = deque()q.appendleft(sa(sx, sy))dist[sx][sy] = 0while len(q):t = q.pop()x, y = t.x, t.yfor i in range(4):x1 = x + dx[i]y1 = y + dy[i]if x1 < 1 or x1 > n or y1 < 1 or y1 > n:continueif dist[x1][y1] > dist[x][y] + 1:dist[x1][y1] = dist[x][y] + 1q.appendleft(sa(x1, y1))for num in g[pos_to_num(x, y)]:x1, y1 = num_to_pos(num)if dist[x1][y1] > dist[x][y] + 1:dist[x1][y1] = dist[x][y] + 1q.appendleft(sa(x1, y1))ans = 0bfs(n, n)for i in range(1, n + 1):for j in range(1, n + 1):ans += dist[i][j]print(f'{ans / (n * n):.2f}')

第二种

'''
Author: NEFU AB-IN
Date: 2023-05-25 15:59:24
FilePath: \LanQiao\2222\2222.1.py
LastEditTime: 2023-05-25 16:35:58
'''
# import
from sys import setrecursionlimit, stdin, stdout, exit
from collections import Counter, deque
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from bisect import bisect_left, bisect_right
from datetime import datetime, timedelta
from string import ascii_lowercase, ascii_uppercase
from math import log, gcd, sqrt, fabs, ceil, floorclass sa:def __init__(self, x, y, w):self.x = xself.y = yself.w = w# Final
N = int(2e3 + 10)
M = int(5e6 + 10)
INF = int(2e9)# Define
setrecursionlimit(INF)
input = lambda: stdin.readline().rstrip("\r\n")  # Remove when Mutiple data
read = lambda: map(int, input().split())
LTN = lambda x: ord(x.upper()) - 65  # A -> 0
NTL = lambda x: ascii_uppercase[x]  # 0 -> A# —————————————————————Division line ——————————————————————dx = [0, -1, 0, 1]
dy = [-1, 0, 1, 0]g = [[] for _ in range(M)]
dist = [[0] * N for _ in range(N)]
st = [[0] * N for _ in range(N)]def pos_to_num(x, y):x -= 1y -= 1return x * n + ydef num_to_pos(num):return [num // n + 1, num % n + 1]n, m = read()
for i in range(m):x1, y1, x2, y2 = read()g[pos_to_num(x1, y1)].append(pos_to_num(x2, y2))g[pos_to_num(x2, y2)].append(pos_to_num(x1, y1))def bfs(sx, sy):q = deque()q.appendleft(sa(sx, sy, 0))st[sx][sy] = 1while len(q):t = q.pop()x, y, w = t.x, t.y, t.wfor i in range(4):x1 = x + dx[i]y1 = y + dy[i]if x1 < 1 or x1 > n or y1 < 1 or y1 > n or st[x1][y1]:continuest[x1][y1] = 1q.appendleft(sa(x1, y1, w + 1))dist[x1][y1] = w + 1for num in g[pos_to_num(x, y)]:x1, y1 = num_to_pos(num)if st[x1][y1]:continuest[x1][y1] = 1q.appendleft(sa(x1, y1, w + 1))dist[x1][y1] = w + 1ans = 0bfs(n, n)for i in range(1, n + 1):for j in range(1, n + 1):ans += dist[i][j]print(f'{ans / (n * n):.2f}')