2222. 迷宫
摘要
Title: 2222. 迷宫
Tag: BFS、最短路、坐标
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
2222. 迷宫
-
题意
摘要：终点为n,n，存在传送门，代价与走动代价相同，均为1，起点不定，求从初始格子走到终点的最短 步数的期望值是多少
-
思路
两种写法，但都以BFS为基础
- 总体思路：要求求出所有点到终点的距离之和，所以我们反向思考，使用BFS以终点为起点跑遍整个地图,每次到一个新的位置时，此时到达的步数就是从终点到该点的最短步数，反过来也是从该点到终点的最短步数。为什么一定会是最短呢？因为BFS自带最短路效应。至于传送门采用二维坐标压缩至一维坐标，把坐标基准更改为[0, 0]，方便取余和整除
- 第一种：采用最短路策略，不用st数组，因为每个坐标可能走多次（当然在第一种思路中已经用st数组回避这个可能了），所以每次就得计算最短花费，dist初始化均为INF
- 第二种：以总体思路为标准，直接BFS，用到dist和st数组，其中dist数组其实可以省略（因其记录的是BFS层数，所以可以边遍历边加）
-
代码
第一种
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89# 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, floor
class sa:
def __init__(self, x, y):
self.x = x
self.y = y
def __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 -= 1
y -= 1
return x * n + y
def 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] = 0
while len(q):
t = q.pop()
x, y = t.x, t.y
for i in range(4):
x1 = x + dx[i]
y1 = y + dy[i]
if x1 < 1 or x1 > n or y1 < 1 or y1 > n:
continue
if dist[x1][y1] > dist[x][y] + 1:
dist[x1][y1] = dist[x][y] + 1
q.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] + 1
q.appendleft(sa(x1, y1))
ans = 0
bfs(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}')
第二种
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96'''
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, floor
class sa:
def __init__(self, x, y, w):
self.x = x
self.y = y
self.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 -= 1
y -= 1
return x * n + y
def 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] = 1
while len(q):
t = q.pop()
x, y, w = t.x, t.y, t.w
for 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]:
continue
st[x1][y1] = 1
q.appendleft(sa(x1, y1, w + 1))
dist[x1][y1] = w + 1
for num in g[pos_to_num(x, y)]:
x1, y1 = num_to_pos(num)
if st[x1][y1]:
continue
st[x1][y1] = 1
q.appendleft(sa(x1, y1, w + 1))
dist[x1][y1] = w + 1
ans = 0
bfs(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}')