2014
11-05

PAINTING

We are going to cover a wall (whose area is r*c) with m different kinds of oil paint ( that is also m kinds of colors ). In order to simplify the problem, we will regard the wall as a set of r*c small squares. The area of one small square is 1 and a small square could be expressed as (x , y) (1<=x<=r, 1<=y<=c).
So every time when we are painting some selected area, we are covering the small squares in that area with a particular color.
Your task is to calculate the number of colors which are completely covered after m times of painting.
For example, given a rectangular area of a upper left corner (x1, y1) and a lower right corner (x2, y2)

Multiple test cases, end with EOF.
In every test case:
In the first line, there will be 3 integers: r c m. r and c are the length and width of the wall , and m is the number of colors of the oil paint. Each type of the oil paints has its own different color.
Then there will be m lines followed, and the ith line has 4 integers: x1 y1 x2 y2, which means that we will cover the rectangular area of a upper left corner (x1, y1) and a lower right corner (x2, y2) with the ith color.

Multiple test cases, end with EOF.
In every test case:
In the first line, there will be 3 integers: r c m. r and c are the length and width of the wall , and m is the number of colors of the oil paint. Each type of the oil paints has its own different color.
Then there will be m lines followed, and the ith line has 4 integers: x1 y1 x2 y2, which means that we will cover the rectangular area of a upper left corner (x1, y1) and a lower right corner (x2, y2) with the ith color.

3 3 3
1 1 2 2
1 3 3 3
1 1 3 3

2

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int r, c, m;
int mark[953][957];
bool f[1000];

int main()
{
while(~scanf("%d%d%d", &r, &c, &m))
{
int minx = 2000, miny = 2000, maxx = 0, maxy = 0;
memset(mark, 0, sizeof(mark));
memset(f, 0, sizeof(f));
for(int i = 1; i <= m; i++)
{
int x1, x2, y1, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
minx = x1 < minx ? x1 : minx;
minx = x2 < minx ? x2 : minx;
maxx = x1 > maxx ? x1 : maxx;
maxx = x2 > maxx ? x2 : maxx;
miny = y1 < miny ? y1 : miny;
miny = y2 < miny ? y2 : miny;
maxy = y1 > maxy ? y1 : maxy;
maxy = y2 > maxy ? y2 : maxy;
for(int x = x1; x <= x2; x++)
for(int y = y1; y <= y2; y++)
mark[x][y] = i;
}
int ans = 0;
for(int x = minx; x <= maxx; x++)
for(int y = miny; y <= maxy; ++y)
if(!f[mark[x][y]]) f[mark[x][y]] = true;
for(int i = 1; i <= m; ++i)
if(f[i]) ans++;
printf("%d\n", m - ans);
}
return 0;
}

1. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。

2. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮