A32399.Vertex Verse
普及/提高-
官方
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
"In the space between points lies the strategy, where connections form the foundation of victory."
游戏 Vertex Verse 在学生群体之间风靡起来了。Vertex Verse 的游戏规则非常简单:
- 游戏的棋盘是一个每一列有 n 个顶点,每一行有 m 个顶点组成的大小为 n×m 的格点图。其中,第 i 行第 j 列的格点可以被描述为一个有序实数对 (xi,yj) 。
- 游戏需要由两名玩家分别进行操作。 每次操作选中格点图中相邻的两个格点 (a,b) 和 (c,d) 并用一条线将这两个点连接起来。两个格点相邻有且仅当 ∣a−c∣+∣b−d∣=1。
- 当某一位玩家执行完操作后,若棋盘上的最小正方形的数量增加了 k,那么该玩家获得 k 分。棋盘上的一个最小正方形指的是一个面积为 1 的正方形,该正方形的四条边是由有玩家操作后在图上留下的线条所形成的。
给定一场比赛两位玩家(Macw 和 Alex)的操作,请你求出两位玩家分别可以获得的分数。
输入格式
输入包含多行。
第一行输入一个整数 n,m,q,分别表示棋盘的大小和每个人的操作次数。
接下来有 2q 行,每一行有四个数字 a,b,c,d。其中每两行为一个整体进行读入,每一个整体的第一行表示 Macw 选则了两个点 (a,b)(c,d) 并连接,第二行表示 Alex 选择了两个点 (a,b)(c,d)并连接。
输出格式
输出一行两个整数,用空格分开。分别表示 Macw 和 Alex 两人做完所有操作所获得的分数。
输入输出样例
输入#1
2 3 3 1 1 1 2 1 1 2 1 1 2 1 3 1 3 2 3 2 2 2 3 1 2 2 2
输出#1
0 1
输入#2
5 5 12 1 1 1 2 1 2 2 2 2 1 3 1 3 1 3 2 2 2 2 3 2 3 2 4 2 3 3 3 2 4 1 4 1 5 2 5 3 4 3 5 2 5 3 5 3 4 4 4 3 3 4 3 5 4 5 5 3 2 4 2 4 2 5 2 4 1 5 1 5 2 5 3 5 3 5 4 4 5 5 5 3 2 3 3 2 2 3 2 2 1 2 2 1 1 2 1
输出#2
1 2
说明/提示
数据范围与约定:
对于100%的数据,保证 1≤n,m≤500。
对于100%的数据,保证 1≤2q≤10000≤n(n−1)+m(m−1)。
对于100%的数据,保证输入数据合法。
样例一解释:
棋盘的初始状态:
每一回合的棋盘情况如下图所示,其中黄色代表先手 Macw,蓝色代表后手 Alex。
Macw 先手操作:
Alex 后手操作:
Macw 先手操作:
Alex 后手操作:
Macw 先手操作:
Alex 后手操作:
结束后,Alex 获得了一分(蓝色阴影部分是新增的最小正方形)。