Editorial for Clue Contest 05 - Khoảng cách ngắn nhất
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Authors: ,
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()
Comments