i) Покрытие прямоугольниками. Клетчатое прямоугольное поле размером n*m, некоторые клетки которого вырезаны, требуется покрыть минимальным количеством прямоугольников. Прямоугольники не могут пересекаться, выходить за пределы (границы) поля и должны быть параллельны
осям координат.
Вот пример моего решения:
| C++ |
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
| #include "stdafx.h"
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <ctime>
using namespace std;
ifstream infile("input.txt");
void main()
{
setlocale(LC_ALL, "rus");
srand(time(NULL));
int N = 0;
int M = 0;
int matr[20][20];
int time_matr[20][20];
int true_matr[20][20];
int v;
cout << "1.Рандомная генерация" << endl << "2.Ввод матрицы с файла" << endl;
cin >> v;
if (v == 1) {
cout << "Введите кол-во строк N : ";
cin >> N;
if (N < 1 || N > 10) { cout << "Ошибка ввода" << endl; system("pause"); exit(0); }
cout << "Введите кол-во столбцов M : ";
cin >> M;
int random = 0;
random = rand() % 5;
if (M < 1 || M >10) { cout << "Ошибка ввода" << endl; system("pause"); exit(1); }
cout << "Исходная матрица: " << endl;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
if (j == random) { matr[i][j] = 0; random = rand() % 7; }
else { matr[i][j] = 1; random = rand() % 7; }
time_matr[i][j] = matr[i][j];
cout << matr[i][j] << " ";
}
cout << endl;
}
}
if (v == 2){
cout << "Введите кол-во строк N : ";
infile >> N;
if (N < 1 || N >10) { cout << "Ошибка ввода" << endl; system("pause"); exit(0); }
cout << "Введите кол-во столбцов M : ";
infile >> M;
if (M < 1 || M >10) { cout << "Ошибка ввода" << endl; system("pause"); exit(1); }
cout << "Исходная матрица: " << endl;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
infile >> matr[i][j];
/*if(i!=(0||1)&&j!=(0||1))
{
cout << "Ошибка ввода,только нули и единицы";
}
else*/
time_matr[i][j] = matr[i][j];//исходная матрица
cout << matr[i][j] << " ";
}
cout << endl;
}
}
int min_num = 0;
int stroka_num = 0;
int place[100] = { 0 };
int num_coube[100] = { 0 };
bool new_pent = true;
int kount = 0;
int pent_stroka[20] = { 0 };
int prk = 0;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
if (matr[i][j] == 1 && new_pent == true)
{
place[kount] = j;
new_pent = false;
prk++;
}
if (matr[i][j] == 1 && new_pent == false)
{
num_coube[kount]++;
}
else
{
new_pent = true;
kount++;
}
}
pent_stroka[i] = prk;
prk = 0;
new_pent = true;
kount++;
}
int kek = 0;
for (int i = 0; i < N; i++)
{
cout << "Строка № " << i << endl;
cout << "Число прямоугольников: " << pent_stroka[i] << endl;
stroka_num = stroka_num + pent_stroka[i];
for (int k = 0; k < pent_stroka[i]; k++)
{
if (num_coube[kek] != 0)
{
cout << place[kek] << "," << num_coube[kek];
cout << " ";
}
else { k--; }
kek++;
}
cout << endl;
}
cout << "Текущий минимум прямоугольников: " << min_num << endl;
cout << "Текущий максимум прямоугольников: " << stroka_num << endl;
cout << "************************************" << endl;
int kek2 = 0;
for (int i = 0; i < N; i++)
{
min_num = min_num + pent_stroka[i];
for (int k = 0; k < pent_stroka[i]; k++)
{
if (num_coube[kek2] != 0)
{
if (i != 0) {
for (int l = 0; l < pent_stroka[i - 1]; l++)
{
if (place[kek2] == place[kek2 + l - k - pent_stroka[i - 1]] && num_coube[kek2] <= num_coube[kek2 + l - k - pent_stroka[i - 1]])
{
min_num--;
}
}
}
}
else { k--; }
kek2++;
}
cout << "Строк просмотрено: " << i + 1 << endl;
cout << "Текущий минимум прямоугольников: " << min_num << endl;
}
cout << "Наименьшее число прямоугольников: " << min_num << endl;
system("pause");
} |
|
но не могу решить проблему в этом месте:
| C++ |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| for (int i = 0; i < N; i++)
{
min_num = min_num + pent_stroka[i];
for (int k = 0; k < pent_stroka[i]; k++)
{
if (num_coube[kek2] != 0)
{
if (i != 0) {
for (int l = 0; l < pent_stroka[i - 1]; l++)
{
if (place[kek2] == place[kek2 + l - k - pent_stroka[i - 1]] && num_coube[kek2] <= num_coube[kek2 + l - k - pent_stroka[i - 1]])
{
min_num--;
}
}
}
}
else { k--; }
kek2++;
} |
|
здесь сравниваются маски для строк(они имеют вид (a,b), где a - позиция в строке, b - колчиство 1 начиная с нее(0-выколотая клетка, 1 свободная) удачно проходят не все тесты. Например этот:
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 0 1 0 1 0 1
1 0 1 0 1 0 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 0 0 1
1 1 1 1 1 1 1
1 1 1 1 0 0 1
1 1 1 1 1 1 1
какие дополнительные проверки нужно добавить при сравнении масок?
Кроме того интересен метод решения данной задачи методом ветвей и границ
(
