[USACO 2009 Oct G]The Robot Plow

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 (1 <= X <= 240; 1 <= Y <= 240). Each of the I (1 <= I <= 200) plow instructions comprises four integers: Xll, Yll, Xur, and Yur (1 <= Xll <= Xur; Xll <= Xur <= X; 1 <= Yll <= Yur; Yll <= Yur <= Y) 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.

POINTS: 25

#include<bits/stdc++.h> using namespace std; int e[300][300]; int main() { int x,y,n; scanf("%d%d%d",&x,&y,&n); while(n--){ int t1,t2; int t3,t4; scanf("%d%d%d%d",&t1,&t2,&t3,&t4); for(int i=t1;i<=t3;i++){ for(int j=t2;j<=t4;j++) e[i][j]++; } } int ans=0; for(int i=1;i<=x;i++){ for(int j=1;j<=y;j++) if(e[i][j]) ans++; } printf("%d",ans); }

#include<bits/stdc++.h> using namespace std; bool b[241][241]; int main() { int n,m,l,x1,x2,y1,y2,ans=0; cin>>n>>m>>l; while(l--) { cin>>x1>>y1>>x2>>y2; for(int i=x1;i<=x2;i++) for(int j=y1;j<=y2;j++) { if(!b[i][j]) ans++; b[i][j]=1; } } cout<<ans; return 0; }

var a:array[0..241,0..241] of longint; n,m,k,i,j,s,x1,x2,y1,y2,z:longint; begin read(n,m,k); for s:=1 to k do begin read(x1,y1,x2,y2); for i:=x1 to x2 do for j:=y1 to y2 do if a[i,j]=0 then begin inc(z); a[i,j]:=1; end; end; writeln(z); end.

详情