hzCPPOJ

犁田机器人

时间限制:  1 s      内存限制:   128 MB
提交:13     正确:11     分值:98

题目描述

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个指令。


* Line 1: Three space-separated integers: X, Y, and I
* Lines 2..I+1: Line i+1 contains plowing instruction i which is described by four integers: Xll, Yll, Xur, and Yur

输出

* Line 1: A single integer that is the total number of squares plowed

第一行:  一个单独的整数表示被犁过的方格数。

样例

样例输入:
6 4 2 1 1 2 4 1 3 5 4
样例输出:
14

提示

一个数组标记题图,以及耕过的地标记为1,否则为0.最后统计地图中1的个数即可。

提交人

USACO09OCT

来源/分类