6126 : BFS 최적화
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
N×M 크기의 대용량 격자 맵 정보와 다중 시작-도착 쿼리 Q개가 주어집니다.
시간 초과를 최소화하기 위해 매 쿼리마다 방문 배열 및 큐 데이터 구조의 메모리 재생성을 최소화하고, 최적화 기법을 사용하여 각 쿼리 당 시작점에서 도착점까지의 최단 경로를 구하는 프로그램을 작성하십시오.
시간 초과를 최소화하기 위해 매 쿼리마다 방문 배열 및 큐 데이터 구조의 메모리 재생성을 최소화하고, 최적화 기법을 사용하여 각 쿼리 당 시작점에서 도착점까지의 최단 경로를 구하는 프로그램을 작성하십시오.
입력 설명
첫째 줄에 N, M (1 ≤ N, M ≤ 2,000)이 주어집니다.
다음 N개의 줄에 격자 정보(0: 빈칸, 1: 벽)가 공백 구분되어 주어집니다.
그 다음 줄에 쿼리 수 Q (1 ≤ Q ≤ 10)가 주어지고, 이후 Q줄에 걸쳐 쿼리 좌표인
다음 N개의 줄에 격자 정보(0: 빈칸, 1: 벽)가 공백 구분되어 주어집니다.
그 다음 줄에 쿼리 수 Q (1 ≤ Q ≤ 10)가 주어지고, 이후 Q줄에 걸쳐 쿼리 좌표인
r1 c1 r2 c2가 한 줄에 하나씩 주어집니다. (0-indexed)출력 설명
각 쿼리당 시작점부터 도착점까지 최단 거리를 한 줄에 하나씩 순서대로 출력합니다. 도달 불가 시 -1을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 4
0 0 0 0
1 1 1 0
0 0 0 0
0 1 1 1
3
0 0 2 0
0 0 0 3
0 0 3 0
출력 예시
COPY
복사되었습니다!
복사되었습니다!
8
3
9
도움
방문 표시를 매번 초기화(
visited = Array(N, M, false))하면 대규모 맵에서 쿼리가 반복될 때 시간 초과가 나기 쉽습니다. visit_token = query_index를 활용해 2차원 정수 visited 배열과 비교하는 최적화 기법을 써보십시오.