USACO 2004 February- 농장 Part1 > 문제은행 : 정보올림피아드&알고리즘




2146 : 농장 Part1

제한시간
1000 ms   
메모리제한
0 MB   
해결횟수
2 회   
시도횟수
13 회   

문제

농부 창호는 N(2≤N≤40,000)개의 농장이 있고, 각각 1부터 N까지 번호가 매겨져 있다. 그리고 M(1≤M≤40,000)개의 가로 또는 세로로 된 도로들이 농장들을 잇고 있다(각 도로의 길이는 1 이상 1,000 이하인 정수이다).


각 농장은 동, 서, 남, 북으로 최대 4개의 도로와 연결되어있다. 농장들은 오로지 도로의 양쪽 끝에서만 존재하고, 도로의 중간에 존재하는 농장은 없다. 두 개의 도로가 서로 교차 하는 일도 없고, 두 농장 사이에는 오직 하나의 도로만이 존재한다. 무엇보다 중요한 것은 어떠한 두 농장을 선택하더라도 두 농장 사이의 경로는 단 한 가지만 존재한다는 것이다. 창호는 최근에 농장 지도를 잃어버려서 컴퓨터의 백업 자료로부터 데이터를 복구하려고 한다. 창호의 컴퓨터에 저장된 정보는 아래와 같다.


...


23번 농장에서 17번 농장으로 이르는 북쪽 방향의 길이 10인 도로가 있다.

1번 농장에서 17번 농장으로 이르는 동쪽 방향의 길이 7일 도로가 있다.


...


창호가 컴퓨터에서 자료를 회수하는 동안 이따금씩 친구 농부 철기로부터 아래와 같은 질문을 받는다.


"1번 농장과 23번 농장의 맨해튼 거리는 얼마인가?"


여기서 맨해튼 거리는 x좌표 차이와 y좌표 차이의 합을 의미한다. 위의 질문의 경우 답은 17 이 된다. 질문을 받을 때 자료가 충분치 못하다면 대답을 할 수 없을 것이다. 창호의 컴퓨터에 있는 자료를 차례대로 복구하면서, 철기의 질문에 대해 대답을 하는 프로그램을 작성하자.


입력형식

입력의 첫 줄에 공백으로 구분된 두 개의 정수 N, M이 입력된다.
이후 M개의 줄에 걸쳐 도로의 정보가 입력된다.
각 줄의 첫 번째 숫자와 두 번째 숫자는 도로의 양 끝에 있는 농장의 번호이다. 세 번째 숫자는 도로의 길이를 나타내며, 네 번째 문자는 첫 번째 농장을 기준으로 두 번째 농장의 위치가 어느 방향인지 나타낸다(N은 북쪽, E는 동쪽, W는 서쪽, S는 남쪽).

그 다음 줄에는 K(1≤K≤10,000)가 주어지는데, 이는 철기가 던진 질문의 개수를 나타낸다.

이후 K개의 줄에 걸쳐 철기가 던진 질문에 대한 정보가 입력된다.

각 줄의 첫 번째 숫자와 두 번째 숫자는 맨해튼 거리를 알고 싶은 두 개의 농장 번호를 나타내며, 세 번째 숫자는 철기가 질문을 던질 때 창호가 회수한 데이터의 개수를 나타낸다.


출력형식

철기의 질문마다 맨해튼 거리를 출력한다. 만약 자료가 부족하여 알 수 없다면 -1을 출력한다.


입력 예

7 6
1 6 13 E
6 3 9 E
3 5 7 S
4 1 3 N
2 4 20 W
4 7 2 S
3
1 6 1
1 4 3
2 6 6

출력 예

13
-1
10

Hint!

자료를 하나 복구한 뒤에, 1번 농장과 6번 농장의 거리가 13이라는 것을 알 수 있다.
자료를 세 개 복구한 뒤에도 1번 농장과 4번 농장 사이의 거리는 알 수 없다.
자료를 모두 복구한 뒤에는 2번 농장과 6번 농장의 거리가 10 이라는 것을 알 수 있다.




경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP