题目地址:http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0531

题目大意

三合板

涂色:(日文题目,翻译来自http://www.hankcs.com/program/algorithm/aoj-0531-paint-color.html)为了宣传信息竞赛,要在长方形的三合板上喷油漆来制作招牌。三合板上不需要涂色的部分预先贴好了护板。被护板隔开的区域要涂上不同的颜色,比如上图就应该涂上5种颜色。
请编写一个程序计算涂色数量,输入数据中,保证看板不会被护板全部遮住,并且护板的边一定是水平或垂直的。
输入:
第一个数是宽w(1 ≤ w ≤ 1000000),第二个数是高h(1 ≤ h ≤ 1000000)。
第二行是护板的数量n(1 ≤ n ≤ 1000),接着n行是每个护板的左下角坐标 (x1 , y1 )和右上角坐标 (x2 , y2 ),用空格隔开: x1 , y1 , x2 , y2 (0 ≤ x1< x2 ≤ w, 0 ≤ y1 < y2 ≤ h 都是整数)
招牌的坐标系如下,左下角是 (0, 0) ,右上角是(w, h) , 测试集中的30%都满足w ≤ 100, h ≤ 100, n ≤ 100。

思路

其实就是问划分的区域数量,比上图白色区域块为5块,所以需要5种颜色。

可以用宽度优先搜索,但是区域比较大,存不下这么大的区域所以需要离散化,说白了就是坐标压缩,例如

w:10 h:10 n:1 => w:6 h:4 n:1

0000000000
0000000000
0111111110
0111111110     000000
0000000000  => 011110
0000000000     011110
0000000000     000000
0000000000
0000000000
0000000000

虽然w,h达到1000000,但是木板最多就1000个,这就可以将木板坐标(顶点)压缩映射(离散化)到[0, n)的范围。

这里将题目的坐标转换成一个个格子的坐标,方便压缩。。

AC代码

/*************************************************************************
    > File Name: 0531.cpp
      > Author: Netcan
      > Blog: http://www.netcan666.com
      > Mail: 1469709759@qq.com
      > Created Time: 2016-01-11 一 20:39:44 CST
 ************************************************************************/

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;

int w, h, n;
int x1[1005], x2[1005];
int y1[1005], y2[1005];
bool fld[1003*6][1003*6]; // 保存离散化后的区域,1表示有挡板,0表示可涂色
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
typedef pair<int, int> P;

// 对坐标x1, x2离散化,并返回离散化后的宽度
int compress(int *x1, int *x2, int w) {
    vector<int> xs;
    for(int i=0; i<n; ++i) {
        for(int d=-1; d<=1; ++d) {
            int tx1 = x1[i] + d;
            int tx2 = x2[i] + d;
            if(0<=tx1 && tx1 <w) xs.push_back(tx1);
            if(0<=tx2 && tx2 <w) xs.push_back(tx2);
        }
    }
    sort(xs.begin(), xs.end()); // 排序
    xs.erase(unique(xs.begin(), xs.end()), xs.end()); // 去重

    for(int i=0; i<n; ++i) {
        x1[i] = find(xs.begin(), xs.end(), x1[i]) - xs.begin(); // 将坐标映射到0~n
        x2[i] = find(xs.begin(), xs.end(), x2[i]) - xs.begin();
    }
    return xs.size(); // 返回离散后的宽度
}

void bfs(int x, int y) { // 宽度优先搜索
    queue<P> que;
    que.push(P(x, y));
    while(!que.empty()) {
        P q = que.front(); que.pop();
        fld[q.second][q.first] = true;
        for(int d=0; d<4; ++d) {
            int tx = q.first + dx[d];
            int ty = q.second + dy[d];
            if(tx < 0 || tx >= w || ty< 0 || ty >= h) continue;
            if(fld[ty][tx]) continue;
            que.push(P(tx, ty));
            fld[ty][tx] = true;
        }
    }
}

void debug() {
    memset(fld, 0, sizeof(fld));
    for(int i=0; i<n; ++i) {
        for(int y=y1[i]; y<=y2[i]; ++y)
            for(int x=x1[i]; x<=x2[i]; ++x)
                fld[y][x] = true;
    }
    printf("w:%d h:%d n:%d\n", w, h, n);
    for(int y=0; y<h; ++y) {
        for(int x=0; x<w; ++x)
            printf("%c", fld[y][x]?'1':'0');
        printf("\n");
    }
}

void solve() {
    debug();
    w = compress(x1, x2, w); // 离散化
    h = compress(y1, y2, h); // 离散化
    debug();


    memset(fld, 0, sizeof(fld));
    for(int i=0; i<n; ++i)
        for(int y=y1[i]; y<=y2[i]; ++y)
            for(int x=x1[i]; x<=x2[i]; ++x)
                fld[y][x] = true;
    int ans = 0;
    for(int y=0; y<h; ++y) {
        for(int x=0; x<w; ++x) {
            if(fld[y][x]) continue;
            ++ans;
            bfs(x, y);
        }
    }
    cout << ans <<endl;
}


int main() {
#ifdef Oj
    freopen("0531.in", "r", stdin);
    // freopen("0531.out", "w", stdout);
#endif
    while(cin >> w >> h) {
        if(w==h && w==0) break;
        cin >> n;
        for(int i=0; i<n; ++i) {
            cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
            --x2[i]; // 转换成格子坐标,右上角坐标减1。
            --y2[i];
        }
        solve();
    }
    return 0;
}