问题6948--遥远的奶牛

6948: 遥远的奶牛

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 256 MiB

题目描述

【题目描述】

牛为什么要过马路?一个原因是农民约翰的农场有很多路,他的牛要想到处跑就必须穿过很多路。

FJ的农场被布置成N×N方形的田地网格(2N100),某些相邻的田地(如南北向或东西向)被道路隔开,整个网格的外部周界周围有高高的围栏,防止奶牛离开农场。奶牛可以从任何一块田地自由地移动到任何相邻的田地(北、东、南或西),但除非绝对必要,它们不喜欢穿过马路。

FJ的农场有K头奶牛(1K100,KN^2),每头奶牛位于不同的田地。如果为了让一头奶牛拜访另一头奶牛,必须至少穿过一条马路,那么这一对奶牛被称为“遥远的”。请帮FJ数一数“遥远的”奶牛有多少对。

【输入格式】(countcross.in):

第一行输入包含NKR,接下来的R行描述了存在于相邻田地之间的R条道路。每一行的形式为rcr 'c '(1N范围内的整数),表示(r行,第c)中的田地与(r '行,第c ')中的相邻田地之间的道路。最后的K行表示K头奶牛的位置,每一行都用一行和一列来表示。

【输出格式】(countcross.out):

输出“遥远的”的奶牛对数。

【样例输入】:

3 3 3

2 2 2 3

3 3 3 2

3 3 2 3

3 3

2 2

2 3

样例输出:

2

来源/分类