区域的个数 坐标离散化

缘起

离散化是一种常用的技巧. 这里使用二维离散化技巧处理下面的问题（这是道好题，但是没找到地方提交 QAQ~）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
w*h(1<=w,h<=1e6)的格子上画了n(1<=n<=500)条垂直或者水平的宽度为1的直线. 
求出这些线将格子划分成了多少个区域.

【输入格式】 
第一行包含两个整数：w和h，表示矩阵的列数和行数（行列编号都从1开始）。 
第二行包含一个整数n，表示有n条直线。 
接下来的n行，每行包含四个整数：x1,y1,x2,y2，表示一条直线的列号和行号。

【输出格式】 
一个整数，表示区域数量。

【输入样例】
10 10
5
1 4 6 4
1 8 10 8
4 1 4 10
9 1 9 5
10 6 10 10

【输出样例】
6

分析

求区域问题显然使用dfs. 但是如果裸用dfs的话, book数组100w*100w伤不起. 所以要压缩一下棋盘. 即使用坐标离散化的技巧压缩一下原棋盘而不影响答案. 就像下图这个样子.

你会发现 开6n*6n（每根线段左右留白嘛~）的book数组就足够了.

而至于最后使用的搜索，依旧是bfs而不是dfs, 因为即便是6n(本题到了3000), 数组依旧很大, 为了防止栈溢出, 使用bfs了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
//#include "stdafx.h"

#include <stdio.h>
#include <algorithm>
#include <queue>
using namespace std;
//#define LOCAL
typedef pair<int, int> P; // first是行, second是列

int w,h,n, x[2005], y[2005], xnum, ynum,ans,dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};

struct Seg
{
	int x1,y1, x2,y2; // (x1, y1) 和 (x2, y2) 分别是线段的两个端点的列号和行号
}xs[505];
bool book[3005][3005]; // bfs的数组
int map[3005][3005]; // 离散化后的地图

void discrete()
{
	int xnn = 0, ynn = 0;
	for (int i = 0; i<n;i++)
	{
		for (int d = -1; d<=1; d++) // 因为如果两个坐标差距>1的话, 是需要将其插入的,不然会使得压缩后的图的连通性和原图不符
		{
			int nx1 = xs[i].x1+d;
			if (nx1&&nx1<=w) // 注意, 输入数据是从1开始的,而离散化之后的坐标是从0开始的
			{
				x[xnn++] = nx1;
			}
			int nx2 = xs[i].x2+d;
			if (nx2&&nx2<=w)
			{
				x[xnn++] = nx2;
			}
			int nx3 = xs[i].y1+d;
			if (nx3&&nx3<=h)
			{
				y[ynn++] = nx3;
			}
			int nx4 = xs[i].y2+d;
			if (nx4&&nx4<=h)
			{
				y[ynn++] = nx4;
			}
		}
	}
	sort(x, x+xnn);
	sort(y, y+ynn);
	xnum = unique(x,x+xnn)-x;
	ynum = unique(y, y+ynn)-y;
	for (int i = 0; i<n;i++)
	{
		xs[i].x1 = lower_bound(x,x+xnum, xs[i].x1)-x;
		xs[i].x2 = lower_bound(x,x+xnum, xs[i].x2)-x;
		xs[i].y1 = lower_bound(y,y+ynum, xs[i].y1)-y;
		xs[i].y2 = lower_bound(y,y+ynum, xs[i].y2)-y;
	}
} // 将原图坐标离散化为[0,...,xnum-1]列 [0,...,ynum-1]行的图

void bfs(int i, int j) // 从离散化之后的图的i行j列开始bfs
{
	queue<P> q;
	q.push(P(i,j));
	book[i][j] = true;
	while(!q.empty())
	{
		P front = q.front();
		q.pop();
		for (int x = 0; x<4; x++)
		{
			int ni = front.first+dir[x][0], nj = front.second+dir[x][1]; // 跑到ni行,nj列去
			if (~ni&&ni<ynum&&~nj&&nj<xnum&&!map[ni][nj]&&!book[ni][nj])
			{
				book[ni][nj] = true;
				q.push(P(ni, nj));
			}
		}
	}
}

void setblock(int r1, int c1, int r2, int c2) // 从(r1,c1)到(r2,c2)设置障碍
{
	if (r1!=r2)
	{
		if (r1>r2)
		{
			swap(r1, r2);
			swap(c1,c2);
		} // 确保r1<r2
		for (int i = r1; i<=r2; i++)
		{
			map[i][c1] = 1;
		}
	}
	else
	{
		if (c1>c2)
		{
			swap(r1, r2);
			swap(c1,c2);
		} // 确保c1<c2
		for (int i = c1; i<=c2; i++)
		{
			map[r1][i] = 1;
		}
	}
}

void block() // 设置障碍
{
	for (int i = 0; i<n;i++)
	{
		int x1= xs[i].x1, y1 = xs[i].y1, x2 = xs[i].x2, y2 = xs[i].y2; // 从 (y1,x1)到(y2, x2) (行,列)
		setblock(y1,x1,y2,x2);
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d%d%d", &w, &h, &n);
	x[0] = 1,y[0] = 1;
	for (int i = 0; i<n; i++)
	{
		scanf("%d%d%d%d", &xs[i].x1, &xs[i].y1, &xs[i].x2, &xs[i].y2);
	}
	discrete(); // 离散化之后, 在[0,...,xnum-1]列*[0,...,ynum-1]行的棋盘上
	block(); // 使用线段给图上设置障碍
	for (int i = 0; i<ynum; i++)
	{
		for (int j = 0; j<xnum; j++)
		{
			if (!book[i][j]&&!map[i][j])
			{
				ans++;
				bfs(i,j);
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}

可惜无处提交~