思路：
这题目非常牛逼！是道月赛的题目！看完题目我就放弃了。。直接看解题报告。
解法果然牛逼！
解题报告链接在此：
http://acm.pku.edu.cn/JudgeOnline/images/contestreport/200606/G.htm代码是照着解题报告写的，不过还是很烂，好像3000+ms，实在佩服那些1000ms内的神牛们！
#include <stdio.h>
#define MAX_N 1024
struct queue_node 
{
int y, x;
};
int set[MAX_N][MAX_N], cut[MAX_N][MAX_N];
int N, M;
int left, top, right, bottom;
struct queue_node queue[MAX_N * MAX_N];
int head, tail;
inline int find(int *arr, int idx)
{
static int stk[MAX_N * MAX_N], sp;
for (sp = 0; arr[idx]; idx = arr[idx])
stk[sp++] = idx;
for (sp--; sp >= 0; sp--)
arr[stk[sp]] = idx;
return idx;
}
inline void push(int y, int x)
{
if (x < left || x > right || y < top || y > bottom)
return ;
if (cut[y][x])
return ;
cut[y][x] = 1;
if (cut[y][x - 1] && cut[y][x + 1]) {
set[y][x] = x + 1;
set[y][x - 1] = x + 1;
} else if (cut[y][x - 1])
set[y][x - 1] = x;
else if (cut[y][x + 1])
set[y][x] = x + 1;
queue[tail].y = y;
queue[tail].x = x;
tail++;
}
inline int bfs(int y, int x)
{
x = find(set[y], x);
if (cut[y][x])
x++;
if (x > right)
return 0;
head = tail = 0;
push(y, x);
while (head != tail) {
y = queue[head].y;
x = queue[head].x;
head++;
push(y - 1, x);
push(y + 1, x);
push(y, x - 1);
push(y, x + 1);
}
return 1;
}
int main()
{
int i, j, ans;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d", &N, &M);
while (M--) {
scanf("%d%d%d%d", &left, &top, &right, &bottom);
ans = 0;
for (i = top; i <= bottom; i++)
while (bfs(i, left))
ans++;
printf("%d\n", ans);
}
return 0;
}