Why Did the Cow Cross the Road III

题目描述

奶牛为什么要过马路？嗯，其中一个原因是 Farmer John 的农场里道路太多了，导致奶牛在农场里走动时不可避免地要穿过许多道路。

FJ 的农场被布置成一个 $N \times N$ 的正方形网格田地（$2 \leq N \leq 100$）。某些相邻的田地对（例如南北相邻或东西相邻）之间由道路隔开，并且整个网格的外部边界上有一圈高高的围栏，阻止奶牛离开农场。奶牛可以从任意田地自由移动到任意相邻田地（北、东、南或西），不过除非绝对必要，她们更愿意不穿过道路。

农场上有 $K$ 头奶牛（$1 \leq K \leq 100, K \leq N^2$），每头奶牛位于不同的田地中。如果一头奶牛要去拜访另一头奶牛，必须至少穿过一条道路，则称这对奶牛是“遥远的”。请帮助 FJ 统计遥远奶牛对的数量。

输入格式

输入的第一行包含 $N$、$K$ 和 $R$。接下来的 $R$ 行描述存在于相邻田地之间的 $R$ 条道路。每行形如 $r$ $c$ $r'$ $c'$（取值范围为 $1 \ldots 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

提示

题目来源：Brian Dean

标签: USACO|2017|Silver

来源

USACO|2017|Silver