题解 | TheRobotPlow-牛客假日团队赛13J题

题目描述

Farmer John has purchased a new robotic plow in order to relieve him from the drudgery of plowing field after field after field. It achieves this goal but at a slight disadvantage: the robotic plow can only plow in a perfect rectangle with sides of integer length.
Because FJ's field has trees and other obstacles, FJ sets up the plow to plow many different rectangles, which might end up overlapping. He's curious as to just how many squares in his field are actually plowed after he programs the plow with various plow instructions, each of which describes a rectangle by giving its lower left and upper right x,y coordinates.
As usual, the field is partitioned into squares whose sides are parallel to the x and y axes. The field is X squares wide and Y squares high . Each of the plow instructions comprises four integers: Xll, Yll, Xur, and Yur () which are the lower left and upper right coordinates of the rectangle to be plowed. The plow will plow all the field's squares in the range (Xll..Xur, Yll..Yur) which might be one more row and column than would initially be assumed (depending on how you go about your assumptions, of course).

Consider a field that is 6 squares wide and 4 squares high. As FJ issues a pair of plowing instructions (shown), the field gets plowed as shown by '*' and '#' (normally plowed field all looks the same, but '#' shows which were most recently plowed):
......                               **....                            #####. 
......      (1,1)(2,4)           **....       (1,3)(5,4)       #####.
......                              **....                            **....
......                              **....                           **....
A total of 14 squares are plowed.

14

As in the task's example.

#include<bits/stdc++.h>
#define MAXN 1001
using namespace std;
template <typename T> void read(T &x){
	x=0;int f=1;char ch=getchar();
	for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
	for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+ch-'0';
	x*=f;
}
int n,m,num,xI,yI,xII,yII;
int tot;
bool maz[MAXN][MAXN];
int main(){
	read(m),read(n);
	read(num);
	for(int ti=1;ti<=num;++ti){
		read(xI),read(yI),read(xII),read(yII);
		for(int i=xI;i<=xII;++i)
			for(int j=yI;j<=yII;++j)
				if(!maz[i][j])maz[i][j]=1,++tot;
	}
	printf("%d\n",tot);
 	return 0;
}