AT_njpc2017_b.格子グラフ

通过率:0%

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

现有HH行WW列的点阵图。在该图中,顶点在HH行内垂直排列,在WW列内水平排列,且该图仅在顶部、底部、左侧和右侧的相邻顶点之间有边。

鲸鱼酱想要给这张图的边上色,但是有人做了恶作剧,在NN个顶点上作了'x'的标记。
这让鲸鱼酱很不舒服,所以他决定只给没有'x'标记的顶点的边上色。

现在,鲸鱼酱给所有能上色的边上了色。请问他给多少条边上了色?

第ii个'x'标记记录在(ri,ci)(ri,ci)中。而(a,b)(a, b)代表该图aa行bb列的顶点:左上顶点为(1,1)(1,1),右下顶点为(H,W(H, W)。

请注意,输出可能不在32位整型的范围之内。

输入格式

如下。

H W N
r1 c1
r2 c2
... ... 
rN cN

第一行的整数分别为点阵图的行数HH、列数WW和带有'x'标记的顶点数NN,以空格隔开。

当 N≥1N ≥ 1 时,从第二行到 N+1N + 1 行的每一行都是 'x' 标记的顶点位置的信息,以空格隔开。

(ri,ci)(r_i, c_i) 表示在 rir_i 行、 cic_i 列的顶点的'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≦1051≦H,W≦10^5
  • 0≦N≦1030≦N≦10^3
  • 1≦ri≦H1≦r_i≦H
  • 1≦ci≦W1≦c_i≦W
  • 不会在输入的同一位置指定多个顶点。也就是说,对于所有 ii,j(1≤i<j≤N)j (1 ≤ i <j ≤ N),ri≠rjr_i ≠ r_j 与 ci≠cjc_i ≠ c_j 成立。

样例解释

样例#1

样例#2

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

首页