Untitled
unknown
plain_text
a month ago
5.9 kB
3
Indexable
class Table { int N; int minCounter; std::vector<std::pair<int, std::pair<int, int>>> resArr; std::vector<std::vector<bool>> mainArr; public: Table(int N) : N(N), minCounter(N * N), mainArr(N) { for (int i = 0; i < N; i++) mainArr[i].resize(N); } void insertBlock(int, int, int); void removeBlock(int, int, int); std::pair<int, int> findEmpty(); std::pair<int, bool> findMaxSize(int, int); void chooseBlock(std::vector<std::pair<int, std::pair<int, int>>> &, int, int, int); void primeNumber(); void printAnswer(int scale = 1); void division2(); void division3(); void division5(); }; void Table::printAnswer(int scale) { std::cout << minCounter << '\n'; for (int i = 0; i < minCounter; i++) { std::cout << resArr[i].second.first * scale + 1 << ' ' << resArr[i].second.second * scale + 1 << ' ' << resArr[i].first * scale << '\n'; } } void Table::insertBlock(int m, int x, int y) //Вставка квадрата размером m * m с левым верхним углов в точке (x, y) { for (int i = 0; i < m; i++) { for (int j = 0; j < m; j++) { mainArr[x + i][y + j] = true; } } } void Table::removeBlock(int m, int x, int y) //Вставка квадрата размером m * m с левым верхним углов в точке (x, y) { for (int i = 0; i < m; i++) { for (int j = 0; j < m; j++) { mainArr[x + i][y + j] = false; } } } std::pair<int, int> Table::findEmpty() //Поиск первой свободной ячейки для вставки { for (int i = N / 2; i < N; i++) { for (int j = N / 2; j < N; j++) { if (!mainArr[i][j]) return std::make_pair(i, j); } } return std::make_pair(-1, -1); } std::pair<int, bool> Table::findMaxSize(int x, int y) { for (int i = y + 1; i < N; i++) { if (mainArr[x][i]) { if (N - x == i - y) return std::make_pair(N - x, true); return std::make_pair((N - x > i - y) ? i - y : N - x, false); } } if (N - x == N - y) return std::make_pair(N - x, true); return std::make_pair((N - x > N - y) ? N - y : N - x, false); } void Table::chooseBlock(std::vector<std::pair<int, std::pair<int, int>>> &tmpArr, int counter, int x, int y) { std::pair<int, int> coord = findEmpty(); if (coord.first == -1) { if (tmpArr.size() < minCounter) { resArr = tmpArr; minCounter = tmpArr.size(); } return; } if (counter + 1 >= minCounter) { return; } int tmpBestCounter = minCounter; //поиск места для вставки блока std::pair<int, bool> maxSize = findMaxSize(coord.first, coord.second); //поиск максимального размера блока для вставки на найденное пустое место if (maxSize.second) //Если можно вставить сразу блок максимального размера { tmpArr.push_back(std::make_pair(maxSize.first, coord)); insertBlock(maxSize.first, coord.first, coord.second); chooseBlock(tmpArr, counter + 1, x, y); //вставляем очередной блок removeBlock(maxSize.first, coord.first, coord.second); tmpArr.pop_back(); } else { for (int i = maxSize.first; i >= 1; i--) { if (tmpBestCounter > minCounter && i == 1) continue; tmpArr.push_back(std::make_pair(i, coord)); insertBlock(i, coord.first, coord.second); chooseBlock(tmpArr, counter + 1, x, y); //вставляем очередной блок removeBlock(i, coord.first, coord.second); tmpArr.pop_back(); } } } void Table::primeNumber() //вставка начальных блоков и начало работы бэктрекинга { insertBlock(N / 2 + 1, 0, 0); insertBlock(N / 2, N / 2 + 1, 0); insertBlock(N / 2, 0, N / 2 + 1); int counter = 3; int minCounter = N * N; std::vector<std::pair<int, std::pair<int, int>>> tmpArr; tmpArr.push_back(std::make_pair(N / 2 + 1, std::make_pair(0, 0))); tmpArr.push_back(std::make_pair(N / 2, std::make_pair(N / 2 + 1, 0))); tmpArr.push_back(std::make_pair(N / 2, std::make_pair(0, N / 2 + 1))); chooseBlock(tmpArr, counter, N / 2, N / 2); } void Table::division2() { if (N % 2 == 0) { int N_div = N / 2; std::cout << 4 << '\n'; std::cout << 1 << ' ' << 1 << ' ' << N_div << '\n'; std::cout << N_div + 1 << ' ' << 1 << ' ' << N_div << '\n'; std::cout << 1 << ' ' << N_div + 1 << ' ' << N_div << '\n'; std::cout << N_div + 1 << ' ' << N_div + 1 << ' ' << N_div << '\n'; } } void Table::division3() { int realN = N; int scale = N / 3; N = 3; primeNumber(); printAnswer(scale); } void Table::division5() { int realN = N; int scale = N / 5; N = 5; primeNumber(); printAnswer(scale); } int main() { int N; std::cin >> N; Table table(N); if (N % 2 == 0) { table.division2(); return 0; } //создание "карты" дял стола if (N % 3 == 0) { table.division3(); } else if (N % 5 == 0) { table.division5(); } else { table.primeNumber(); table.printAnswer(); } return 0; }
Editor is loading...
Leave a Comment