首页 > ACM题库 > HDU-杭电 > HDU 3536- PAINTING[解题报告]HOJ
2014
11-05

HDU 3536- PAINTING[解题报告]HOJ

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)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮