실행 시간 제한 | 메모리 제한 |
---|---|
2 초 | 512 MB |
도시는 N×N 정사각형 그리드 형태로 구성되어 있으며 (2 ≤ N ≤ 100), 일부 인접한 구역의 쌍 (예: 북쪽-남쪽 또는 동쪽-서쪽)은 도로로 구분되어 있습니다. 또한 도시 전체 외곽에는 높은 담이 있어, 아이들이 도시를 벗어나지 못하게 합니다.아이들은 어느 인접한 구역 (북, 동, 남, 또는 서)으로든 자유롭게 이동할 수 있지만, 필요한 경우가 아니라면 도로를 건너기를 꺼립니다.
도시에는 K 명의 아이들(1 ≤ K ≤ 100,K ≤ N2)이 있으며 각각 다른 구역에 위치해 있습니다. 한 명의 아이가 다른 아이를 방문하기 위해 최소한 한 개의 도로를 건너야 할 경우, 두 명의 아이는 '먼' 쌍이라고 합니다. 멀리 떨어진 아이들의 먼 쌍의 수를 세는 것을 도와주십시오
첫 번째 입력 줄은 N, K, R을 포함합니다.
그 다음 R 줄은 인접한 구역 쌍 사이에 있는 R 도로를 설명합니다. 각 줄은 r c r' c' (범위 내의 정수 1…N) 형식으로, (r 행, c 열)에 있는 구역와 인접한 구역 (r' 행, c' 열) 사이의 도로를 나타냅니다.
마지막 K 줄은 행과 열을 이용하여 K 아이들의 위치를 나타냅니다.
먼 쌍인 아이들의 수를 출력하십시오.
3 3 3 2 2 2 3 3 3 3 2 3 3 2 3 3 3 2 2 2 3
2
출처: USACO 2017 February Contest, Silver Problem 3. Why Did the Cow Cross the Road III