In the small historical village of Basinia, there is a popular activity in wedding ceremonies called rectangle cutting. During this activity, each close relative of the bride comes and cuts a rectangle in the wedding cake (but does not take a piece). The cake has a rectangular shape. The problem is to count how many pieces are in the cake after rectangle-cutting.
For example, in the following figure, the cake size is 3×5, and three people have made rectangular cuts in it. As a result, the cake is cut into six pieces.
Each rectangular cut is specified by the (x, y) coordinates of its two opposite corners. The input for the above figure can be found in the first sample input. As there are large families in Basinia, the number of pieces may be large and we need a computer program to compute it.
Input
The input contains several test cases. Each test has several lines. The first line has two integers w (1 ≤ w ≤ 20) and h (1 ≤ h ≤ 20) which are the width and height of the cake. The second line contains a single integer n (0 ≤ n ≤ 50) which is the number of people who cut rectangles in the cake. After this, there are n lines each containing the integers x1, y1, x2, y2 which are the coordinates of two opposite corners of the cut. You may assume 0 ≤ x1, x2 ≤ w and 0 ≤ y1, y2 ≤ h. The last line of the input is a line containing two zeros.
Output
For each test case, write the number of pieces the cake is cut into.
Sample Input
3 5
3
1 1 3 2
4 0 2 3
4 0 5 1
6 6
2
2 0 5 3
3 1 4 2
0 0
Sample Output
6
3
題目大意：
給定一個w*h的矩形，在這個矩形里切小矩形，最后計算并輸出封閉圖形的個數。
思路：
把矩形看作w*h個小方塊，第n次切割，就在所切的矩形的方塊上標記數字2^n，如果重復切到同一個方塊就把
標記值累加，這樣標記完后再深搜，就得到封閉圖形個數了。（標記為2^n，是ht同學的思想，很巧妙，但只能使用
于數據量比較小的情況）。同時此題應注意w 和 h 的順序，我在這里耽誤了好久，還wa了一次。
代碼：
Source Code
Problem: 3338 User: wic
Memory: 272K Time: 0MS
Language: C++ Result: Accepted
Source Code
#include<iostream>
using namespace std;
int a[25][25];
int mark=-1,k;
int w,h;
int dir[4][2]=
{{-1,0},{1,0},{0,-1},{0,1}};
int power(int a, int b)//pow的返回值類型不是int，于是自己寫了一個函數
{
int ans=1;
while(b--)
ans*=a;
return ans;
}
bool inside(int x, int y)
{
if(x<=h && x>0 && y<=w && y>0)
return true;
else
return false;
}
void dfs(int x, int y)//自己寫的深搜，嘿嘿
{
for(int i=0; i<4; i++){
int xx=x+dir[i][0];
int yy=y+dir[i][1];
if(inside(xx,yy) && a[yy][xx]!=mark && a[yy][xx]==k){
a[yy][xx]=mark;
dfs(xx,yy);
}
}
}
int main()
{
int i,j,n,x1,y1,x2,y2,maxx,maxy,minx,miny,m;
while(cin>>w>>h && w && h){
memset(a, 0, sizeof(a));
cin>>n;
k=0;
int c=0;
int count=0;
while(n--){
cin>>x1>>y1>>x2>>y2;
maxx=(x1>=x2)?x1:x2;
minx=(x1<=x2)?x1:x2;
maxy=(y1>=y2)?y1:y2;
miny=(y1<=y2)?y1:y2;
m=power(2,c);
for(i=miny+1; i<=maxy; i++)
for(j=minx+1; j<=maxx; j++)
a[i][j]+=m;
c++;
}
k=c;
m=power(2,k);
for(k=0; k<m; k++){
for(i=1; i<=w; i++)
for(j=1; j<=h; j++)
if(a[i][j]!=mark&&a[i][j]==k)
{ dfs(j,i); count++;}
}
cout<<count<<endl;
}
return 0;
}