题目大意：在一个1000000*1000000的矩阵中放入几块木板，问你这些木板把矩阵划分成了几个区域？输入会给左下角和右上角的坐标，输入W==0且H==0结束。
这一题是书上的作业题，书上有一道差不多的例题，但是书上那道例题是用的直线的，而且他的坐标是点格，而这道题是坐标（这个很重要，我一开始没有区分好导致理解不了）。那么这一题肯定要用到坐标压缩的（1000000*1000000太大了，我们可以把木板压缩到最小就可以了），标准的直接看代码就好了，很容易理解。）
然后现在这题很难的一个地方在于，怎么高效地判断和填充木板区域，当然我们可以一个一个木板找，然后匹配填充，但是显然这样比较慢（这种操作复杂度是0(W*H*N)，虽然坐标压缩了以后这个不会很大，但是还是有其他更好的方法的），这里有一个很神奇的imos法，imos法不仅仅是用来做这种ACM的题的，还是一个很实用的工程算法。
imos法详解（中文版，我暂时还没得到原作者的同意，所以直接丢博主的链接好了）
http://www.hankcs.com/program/algorithm/imos_method.html
imos法详解（日文原版，这里有上面中文版没有的imos如何应对特殊的三角形矩阵的填充和一些函数（二次函数，高斯函数）的问题）
http://imoz.jp/algorithms/imos_method.html
（ps:上面两个的那个影响力计算的图是错的（代码没有错），-1的位置错了。）
最后我们用BFS就可以了（DFS容易爆栈，当然你用栈来模拟我没话说）。
#include <iostream>
#include <algorithm>
#include <functional>
#include <string.h>
#include <stdio.h>
#include <vector>
#include <queue>
#define MAX_N 1010 using namespace std; static int X1[], Y1[], X2[], Y2[], fld[MAX_N * ][MAX_N * ],
dx[] = { -, , , }, dy[] = { , -, , }; static int compress(int *const, int *const, const int, const int);
static int bfs(const int, const int);
void imos(const int, const int, const int); int main(void)
{
int W, H, N; //freopen("D:\\input.txt", "r", stdin);
while ()
{
scanf("%d%d", &W, &H);
if (W == && H == )
break;
scanf("%d", &N);
for (int i = ; i < N; i++)
{
scanf("%d%d%d%d", &X1[i], &Y1[i], &X2[i], &Y2[i]);
}
W = compress(X1, X2, W, N);
H = compress(Y1, Y2, H, N); imos(W, H, N);
cout << bfs(W, H) << endl;
}
return EXIT_SUCCESS;
} static int compress(int *const s1, int *const s2, const int W, const int N)
{
//坐标离散化
vector<int>xs; for (int i = ; i < N; i++)
{
if ( < s1[i] && s1[i] < W) xs.push_back(s1[i]);
if ( < s2[i] && s2[i] < W) xs.push_back(s2[i]);
}
xs.push_back();
xs.push_back(W);//加上边界条件
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end()); for (int i = ; i < N; i++)
{
s1[i] = find(xs.begin(), xs.end(), s1[i]) - xs.begin();
s2[i] = find(xs.begin(), xs.end(), s2[i]) - xs.begin();
}
return xs.size() - ;//注意这里要获取的边界条件使得size加了2，要减1才能刚好变成真正的数组长度
} static int bfs(const int W, const int H)
{
int ans = ;
for (int i = ; i < W; i++)
for (int j = ; j < H; j++)
{
if (fld[i][j])continue;//搜索没有挡板的位置
ans++; queue<pair<int, int> > que;
que.push(make_pair(i, j));
while (!que.empty())
{
int tx = que.front().first, ty = que.front().second;
que.pop();
for (int i = ; i < ; i++)
{
int ttx = tx + dx[i], tty = ty + dy[i];
if ( <= ttx && ttx <= W
&& <= tty && tty <= H
&& !fld[ttx][tty])
{
que.push(make_pair(ttx, tty));
fld[ttx][tty] = ;
}
}
}
}
return ans;
} void imos(const int W, const int H, const int N)
{
//imos法统计区间
memset(fld, , sizeof(fld)); for (int i = ; i < N; i++)//统计影响力
{
fld[X1[i]][Y1[i]]++;
fld[X1[i]][Y2[i]]--;
fld[X2[i]][Y1[i]]--;
fld[X2[i]][Y2[i]]++;
}
for (int i = ; i < W; i++)//累计横向
for (int j = ; j < H; j++)
fld[i][j] += fld[i][j - ]; for (int j = ; j < H; j++)//累计纵向
for (int i = ; i < W; i++)
fld[i][j] += fld[i - ][j];
//非零部分就是有挡板的位置了
}
另外吐槽一下AOJ，编译器是个什么鬼编译器，连queue<pair<int,int>>都要报错，居然不能识别pair<int,int>和queue的>的区分，不过AOJ有input和output文件，这个好评
参考：http://www.hankcs.com/program/algorithm/aoj-0531-paint-color.html