03月
16

ZOJ-1017 Treasure Map

发表于 • 本文总阅读数 次
字数统计: 1.1k

二维精确覆盖问题

题目

  https://zoj.pintia.cn/problem-sets/91827364500/problems/91827367871

题意

  给出p个小矩形和每个小矩形的左下角、右上角坐标，问能否用这些小矩形拼成一个m×n的大矩形，拼接的时候小矩形的位置不能改变，且小矩形之间不能重叠。

题目解析

  这是一个二维的精确覆盖问题，可以转化为一维来处理。对于每一个小矩形，将其能覆盖的区域赋值为1，不能覆盖的区域赋值为0，这样就构建了一个m×n的矩阵，然后将这个二维的矩阵转化为一维的向量。转化的方法就是，把矩阵的m行元素按顺利排一行，比如矩阵的第一行的第1、2、…、n-1、n个元素的作为向量的第1、2、…、n-1、n个元素，第二行的第1、2、…、n-1、n个元素作为向量的第n+1、n+2、….、2n-1、2n个元素，第i行的第j个元素的作为第i×n+j元素。接下来将p个小矩形转化成的p个向量组成一个p行m×n列的的矩阵，这样题目就转化为对这个矩阵求标准的精确覆盖问题，用舞蹈链算法处理一下就好了。
  需要注意的是，这题需要求覆盖整个大矩形，最少使用的小矩形，求出可行解后需要继续搜索出最优解。

代码

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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
/* https://zoj.pintia.cn/problem-sets/91827364500/problems/91827367871 */
#include <stdio.h>
#include <string.h>

const int MAX_COLS = 30 * 30 + 10;
const int MAX_ROWS = 500 + 10;

typedef struct node
{
	int u, d, l, r;
	int row, col;
} node;

int rows, cols, node_size;
node nd[MAX_ROWS * MAX_COLS];
int row_head[MAX_ROWS], col_nds[MAX_COLS];

int ans;

void init()
{
	int i;

	/* 初始化每一列的头节点 */
	for(i = 0; i <= cols; i++)
	{
		nd[i].u = i;
		nd[i].d = i;
		nd[i].l = i - 1;
		nd[i].r = i + 1;
	}
	nd[0].l = cols;
	nd[cols].r = 0;
	memset(col_nds, 0, sizeof(col_nds));
	node_size = cols + 1;

	/* 初始化每一行的行指针 */
	memset(row_head, -1, sizeof(row_head));
}

void add_node(int row, int col)
{
	/* nd[node_size]为新添加的节点 */
	nd[node_size].row = row;
	nd[node_size].col = col;

	/* 将新添加的节点与其所在的列连接 */
	nd[node_size].u = col;
	nd[node_size].d = nd[col].d;
	nd[nd[col].d].u = node_size;
	nd[col].d = node_size;

	/* 将新添加的节点与其所在的行连接 */
	if(row_head[row] == -1)
	{
		row_head[row] = node_size;
		nd[node_size].l = node_size;
		nd[node_size].r = node_size;
	}
	else
	{
		int row_first = row_head[row];
		nd[node_size].r = row_first;
		nd[node_size].l = nd[row_first].l;
		nd[nd[row_first].l].r = node_size;
		nd[row_first].l = node_size;
	}
	col_nds[col]++;
	node_size++;
}

void remove(int col)
{
	int i, j;

	/* 将第col列从十字链表里移除 */
	nd[nd[col].l].r = nd[col].r;
	nd[nd[col].r].l = nd[col].l;

	/* 将与第col列里节点有关的行移除 */
	for(i = nd[col].d; i != col; i = nd[i].d)
	{
		for(j = nd[i].r; j != i; j = nd[j].r)
		{
			nd[nd[j].u].d = nd[j].d;
			nd[nd[j].d].u = nd[j].u;
			col_nds[nd[j].col]--;
		}
	}
}

void resume(int col)
{
	int i, j;

	/* 将第col列从十字链表里恢复 */
	nd[nd[col].l].r = col;
	nd[nd[col].r].l = col;

	/* 将与第col列里节点有关的行恢复 */
	for(i = nd[col].d; i != col; i = nd[i].d)
	{
		for(j = nd[i].r; j != i; j = nd[j].r)
		{
			nd[nd[j].u].d = j;
			nd[nd[j].d].u = j;
			col_nds[nd[j].col]++;
		}
	}
}

void dfs(int len)
{
	int i, j, res, select_col;
	int min;

	if(len >= ans)
	{
		return ;
	}
	/* 当前十字链表没有列 */
	if(nd[0].r == 0)
	{
		ans = len;
		return ;
	}
	min = MAX_ROWS;
	for(i = nd[0].r; i != 0; i = nd[i].r)
	{
		if(nd[i].d == i)
		{
			return ;
		}
		if(min > col_nds[i])
		{
			select_col = i;
			min = col_nds[i];
		}
	}
	remove(select_col);
	for(i = nd[select_col].d; i != select_col; i = nd[i].d)
	{
		for(j = nd[i].r; j != i; j = nd[j].r)
		{
			remove(nd[j].col);
		}
		dfs(len + 1);
		for(j = nd[i].l; j != i; j = nd[j].l)
		{
			resume(nd[j].col);
		}
	}
	resume(select_col);
}

int main()
{
	int t, n, m, p, x1, x2, y1, y2;
	int i, j, k, len;

	scanf("%d", &t);
	while(t--)
	{
		scanf("%d %d %d", &n, &m, &p);
		rows = p;
		cols = n * m;
		init();
		for(k = 0; k < p; k++)
		{
			scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
			for(i = y1; i < y2; i++)
			{
				for(j = x1; j < x2; j++)
				{
					add_node(k + 1, i * n + j + 1);
				}
			}
		}
		ans = MAX_ROWS;
		dfs(0);
		if(ans == MAX_ROWS)
		{
			ans = -1;
		}
		printf("%d\n", ans);
	}
	return 0;
}
分享到：
0%