AT_njpc2017_b.格子グラフ
通过率:0%
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
现有H行W列的点阵图。在该图中,顶点在H行内垂直排列,在W列内水平排列,且该图仅在顶部、底部、左侧和右侧的相邻顶点之间有边。
鲸鱼酱想要给这张图的边上色,但是有人做了恶作剧,在N个顶点上作了'x'的标记。
这让鲸鱼酱很不舒服,所以他决定只给没有'x'标记的顶点的边上色。
现在,鲸鱼酱给所有能上色的边上了色。请问他给多少条边上了色?
第i个'x'标记记录在(ri,ci)中。而(a,b)代表该图a行b列的顶点:左上顶点为(1,1),右下顶点为(H,W)。
请注意,输出可能不在32位整型的范围之内。
输入格式
如下。
H W N
r1 c1
r2 c2
... ...
rN cN
第一行的整数分别为点阵图的行数H、列数W和带有'x'标记的顶点数N,以空格隔开。
当 N≥1 时,从第二行到 N+1 行的每一行都是 'x' 标记的顶点位置的信息,以空格隔开。
(ri,ci) 表示在 ri 行、 ci 列的顶点的'x'标记。
输出格式
输出鲸鱼酱绘制的边数。
输入输出样例
输入#1:
3 4 4
1 4
2 2
2 4
3 1
输出#1:
7
输入#2:
1 5 2
1 2
1 4
输出#2:
(原题缺失)
输入#3:
100000 100000 0
输出#3:
19999800000
输入输出样例
输入#1
3 4 4 1 4 2 2 2 4 3 1
输出#1
7
输入#2
1 5 2 1 2 1 4
输出#2
0
输入#3
100000 100000 0
输出#3
19999800000
说明/提示
- 保证输入全是整数。
- 1≦H,W≦105
- 0≦N≦103
- 1≦ri≦H
- 1≦ci≦W
- 不会在输入的同一位置指定多个顶点。也就是说,对于所有 i,j(1≤i<j≤N),ri=rj 与 ci=cj 成立。
样例解释
样例#1

样例#2

输入解题思路,AI测评打分。不知道怎么写?