1+ import sys
2+ from collections import deque
3+ input = sys .stdin .readline
4+
5+ N , M = map (int , input ().split ())
6+ board = [list (map (int , input ().split ())) for _ in range (N )]
7+ store = {}
8+ distance = [[[0 ]* N * N for _ in range (N )] for _ in range (N )]
9+ camp = []
10+ people = deque ()
11+ time = 0
12+
13+ for i in range (M ):
14+ r , c = map (int , input ().split ())
15+ store [i ] = (r - 1 , c - 1 )
16+
17+ for i in range (N ):
18+ for j in range (N ):
19+ if board [i ][j ] == 1 :
20+ camp .append ((i , j ))
21+ continue
22+
23+ def calc_dist ():
24+ dx , dy = [0 , 0 , - 1 , 1 ], [1 , - 1 , 0 , 0 ]
25+
26+ for i in range (N ):
27+ for j in range (N ):
28+ check = [[0 ] * N for _ in range (N )]
29+ check [i ][j ] = 1
30+ q = deque ([(i , j , 0 )])
31+
32+ while q :
33+ x , y , cnt = q .popleft ()
34+
35+ for d in range (4 ):
36+ nx , ny = x + dx [d ], y + dy [d ]
37+
38+ if 0 <= nx < N and 0 <= ny < N and not check [nx ][ny ]:
39+ check [nx ][ny ] = 1
40+ if board [nx ][ny ] == 3 : continue
41+
42+ num = nx * N + ny
43+ distance [i ][j ][num ] = cnt + 1
44+ q .append ((nx , ny , cnt + 1 ))
45+
46+ def move_people (t , x , y ):
47+ dx , dy = [- 1 , 0 , 0 , 1 ], [0 , - 1 , 1 , 0 ]
48+ store_num = store [t ][0 ] * N + store [t ][1 ]
49+ dist = 10000000000
50+ mx , my = 0 , 0
51+
52+ for d in range (4 ):
53+ nx , ny = x + dx [d ], y + dy [d ]
54+
55+ if 0 <= nx < N and 0 <= ny < N :
56+ if nx == store [t ][0 ] and ny == store [t ][1 ]:
57+ board [nx ][ny ] = 3
58+ return 1
59+ elif board [nx ][ny ] == 3 :
60+ continue
61+ elif dist > distance [nx ][ny ][store_num ]:
62+ dist = distance [nx ][ny ][store_num ]
63+ mx , my = nx , ny
64+
65+ people .append ((t , mx , my ))
66+ return 0
67+
68+ # t시간에 사람 한명 베이스캠프로
69+ def get_basecamp ():
70+ global time
71+ r , c = store [time - 1 ]
72+ store_num = r * N + c
73+
74+ basecamp_dist = 10000000000
75+ br , bc = 0 , 0
76+
77+ for x , y in camp :
78+ if board [x ][y ] == 3 : continue
79+ dist = distance [x ][y ][store_num ]
80+ if basecamp_dist < dist :
81+ continue
82+ elif basecamp_dist > dist :
83+ br , bc = x , y
84+ basecamp_dist = dist
85+ else :
86+ if br < x : continue
87+ elif br > x : br , bc = x , y
88+ elif bc < y : continue
89+ else : br , bc = x , y
90+
91+ board [br ][bc ] = 3
92+ people .append ((time - 1 , br , bc ))
93+
94+ calc_dist ()
95+ not_arrive = M
96+
97+ while not_arrive :
98+ time += 1
99+ p = people
100+ people = deque ()
101+
102+ while p :
103+ t , x , y = p .popleft ()
104+ is_arrive = move_people (t , x , y )
105+ not_arrive -= is_arrive
106+ if is_arrive : calc_dist ()
107+
108+ if time <= M :
109+ get_basecamp ()
110+ calc_dist ()
111+
112+ print (time )
0 commit comments