1293 问题 D: 犁田的机器人

时间限制: 1s 内存限制: 128MB 提交: 106 解决: 0
题目描述

Farmer John为了让自己从无穷无尽的犁田工作中解放出来,于是买了个新机器人帮助他犁田。这个机器人可以完成犁田的任务,可惜有一个小小的缺点:这个犁田机器人一次只能犁一个边的长度是整数的长方形的田地。

因为FJ的田地有树和其他障碍物,所以FJ设定机器人去犁很多不同的长方形。这些长方形允许重叠。他给机器人下了P个指令,每个指令包含一个要犁长方形的地。这片田地由长方形的左下角和右上角坐标决定。他很好奇最后到底有多少个方格的地被犁过了。

一般来说,田地被分割为很多小方格。这些方格的边和x轴或y轴平行。田地的宽度为X个方格,高度为Y个方格(1 < = X < = 240; 1 < = Y < = 240)。FJ执行了I (1 < = I < = 200)个指令,每个指令包含4个整数:Xll, Yll, Xur, Yur (1 < = Xll < = Xur; Xll < = Xur < = X; 1 < = Yll < = Yur; Yll < = Yur < = Y),分别是要犁的长方形的左下角坐标和右上角坐标。机器人会犁所有的横坐标在Xll..Xur并且纵坐标Yll..Yur范围内的所有方格的地。可能这个长方形会比你想像的多一行一列(就是说从第Xll列到第Xur列一共有Xur - Xll + 1列而不是Xur - Xll列)。

考虑一个6方格宽4方格高的田地。FJ进行了2个操作(如下),田地就被成"*"和"#"了。虽然一般被犁过的地看起来都是一样的。但是标成"#"可以更清晰地看出最近一次被犁的长方形。

...... **.... #####.

...... (1,1)(2,4) **.... (1,3)(5,4) #####.

...... **.... **....

...... **.... **....

一共14个方格的地被犁过了。

输入

第一行:三个由空格隔开的整数:X,  Y,  I

第二行到第I+1行:第i+1行有四个整数Xll, Yll, Xur, Yur,表示第i个指令。

输出
第一行:一个单独的整数表示被犁过的方格数。
样例输入
6 4 2
1 1 2 4
1 3 5 4
样例输出
14
提示
零基础同学可以先学习视频课程,包含C/C++、Python、百练、蓝桥杯辅导、算法数据结构等课程,提供视频讲解以及配套习题,还有老师答疑,点击这里了解课程详情

比赛公告

一如以往~本次月赛  第二名有奖!! 没错!第二名!!!