Hướng dẫn giải của Clue Contest 05 - Khoảng cách ngắn nhất
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Tác giả: ,
Subtask 1: ~n, m \le 60~
Ở subtask này, ta sẽ brute-force giá trị ~d~ từ ~0~ đến ~m + n~. Với mỗi thiết bị điện tử, ta sẽ duyệt toàn bộ máy phát để kiểm tra.
ĐPT: ~O~(~n \times m \times (n + m)~)
Subtask 2: ~n, m \le 250~
Đây là subtask tối ưu từ subtask 1. Thay vì ta sẽ brute-force giá trị ~d~, ta sử dụng thuật toán tìm kiếm nhị phân để tìm nhanh giá trị ~d~.
ĐPT: ~O~(~n \times m \times log(n + m)~)
Subtask 3: ~n, m \le 900~
Để giải được subtask này, người đọc cần biết về BFS đa nguồn (Multi-source BFS).
Ta sẽ BFS từ tất cả máy phát cùng một lúc. Gọi ~dis_{i, j}~ là khoảng cách từ ô ~(i, j)~ đến máy phát gần nhất.
Kết quả chính là max của mọi ~dis_{i, j}~ với điều kiện ~(i, j)~ là tọa độ của thiết bị điện tử.
ĐPT: ~O~(~n \times m~)
Code mẫu:
from collections import deque
import sys
import math
import random
def bfs(n, m, a):
dir = [(-1, 0), (1, 0), (0, -1), (0, 1)]
q = deque()
inf = 10**18
dis = [[inf] * m for _ in range (n)]
for i in range(n):
for j in range(m):
if a[i][j] == 1:
q.append((i, j))
dis[i][j] = 0
while q:
x, y = q.popleft()
for dx, dy in dir:
hx = x + dx
hy = y + dy
if 0 <= hx and hx < n and 0 <= hy and hy < m and dis[hx][hy] == inf:
dis[hx][hy] = dis[x][y] + 1
q.append((hx, hy))
mxx = 0
for i in range(n):
for j in range(m):
if a[i][j] == 2:
mxx = max(mxx, dis[i][j])
if mxx != inf:
return mxx
else:
return -1
def main():
t = int(input())
for _ in range(t):
n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
print(bfs(n, m, a))
if __name__ == "__main__":
main()
Bình luận