RiseOJ – 소는 왜 길을 건넜을까 III

설명

소는 왜 길을 건넜을까? 한 가지 이유는 농부 존의 농장에 도로가 워낙 많아서, 소들이 여러 도로를 건너지 않고는 돌아다닐 수 없기 때문이다.

FJ의 농장은 $N \times N$ 정사각형 격자 모양의 들판들로 이루어져 있다 ( $2 \leq N \leq 100$ ). 인접한 들판의 특정 쌍들(예: 남북 방향 또는 동서 방향)은 도로로 분리되어 있고, 전체 격자의 바깥 둘레에는 높은 울타리가 둘러쳐져 있어 소들이 농장을 떠날 수 없다. 소들은 어떤 들판에서든 인접한(북, 동, 남, 서) 들판으로 자유롭게 이동할 수 있지만, 꼭 필요한 경우가 아니면 도로를 건너지 않는 것을 선호한다.

FJ의 농장에는 $$K$$ 마리의 소가 있으며 ( $1 \leq K \leq 100, K \leq N^2$ ), 각 소는 서로 다른 들판에 있다. 한 소가 다른 소를 만나러 가려면 적어도 하나의 도로를 건너야만 할 때, 그 소 쌍을 "멀리 떨어진" 쌍이라고 한다. 멀리 떨어진 소 쌍의 개수를 세어 FJ를 도와주자.

문제 출처: Brian Dean

제약

문제 출처: Brian Dean

입력 형식

입력의 첫째 줄에 $$N$$ , $$K$$ , $$R$$ 가 주어진다. 다음 $$R$$ 개의 줄은 인접한 들판 쌍 사이에 존재하는 $$R$$ 개의 도로를 나타낸다. 각 줄은 $$r$$ $$c$$ $$r'$$ $$c'$$ ( $1 \ldots N$ 범위의 정수) 형태이며, (행 $$r$$ , 열 $$c$$ )의 들판과 인접한 (행 $$r'$$ , 열 $$c'$$ )의 들판 사이에 도로가 있음을 나타낸다. 마지막 $$K$$ 개의 줄은 $$K$$ 마리 소의 위치를 나타내며, 각각 행과 열로 주어진다.

출력 형식

멀리 떨어진 소 쌍의 개수를 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 countcross.in · 출력을 쓸 파일 countcross.out

예제 1

입력

출력

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2016-2017 > February > Silver

올림피아드 > USACO > 2016-2017 > February > Silver

태그

JudgeUSACO

소는 왜 길을 건넜을까 III

평가 및 의견

풀이 제출