Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <fstream>
- #include <queue>
- #include <array>
- struct Point {
- int x;
- int y;
- };
- int m = 0;
- int r = 0;
- std::vector<std::vector<int>> map;
- bool validatePoint(const Point& point, int color) {
- int x = point.x;
- int y = point.y;
- bool flag = false;
- for (int i = 0; i < r; ++i) {
- std::array<int, 4> arr{map[y - i][x], map[y][x - i], map[y - r + 1][x - i], map[y - i][x - r + 1]};
- for (auto& p : arr) {
- if (p == -1) {
- return false;
- }
- if (color < p || p == 0) {
- flag = true;
- }
- }
- }
- if (flag) {
- for (int i = 0; i < r; ++i) {
- for (int j = 0; j < r; ++j) {
- if (map[point.y - i][point.x - j] == 0 || color < map[point.y - i][point.x - j]) {
- map[point.y - i][point.x - j] = color;
- }
- }
- }
- }
- return flag;
- }
- void validatePoints(std::queue<Point>& points, int color) {
- size_t size = points.size();
- for (size_t i = 0; i < size; ++i) {
- auto& point = points.front();
- if (validatePoint(point, color)) {
- points.emplace(point.x + 1, point.y);
- points.emplace(point.x - 1, point.y);
- points.emplace(point.x, point.y - 1);
- points.emplace(point.x, point.y + 1);
- }
- points.pop();
- }
- }
- int main() {
- std::ifstream input("input.txt");
- if (!input.good()) {
- std::cout << "File error: input.txt\n";
- return 1;
- }
- input >> m >> r;
- map.resize(m + 2);
- for (int i = 0; i < m + 2; ++i) {
- map[i].resize(m + 2);
- }
- for (int i = 0; i < m + 2; ++i) {
- map[0][i] = -1;
- map[i][0] = -1;
- map[m + 1][i] = -1;
- map[i][m + 1] = -1;
- }
- for (int i = 1; i < m + 1; ++i) {
- char c = 0;
- for (int j = 1; j < m + 1; ++j) {
- input >> c;
- map[i][j] = c == '.' ? 0 : -1;
- }
- }
- input.close();
- for (int i = 0; i < r; ++i) {
- for (int j = 0; j < r; ++j) {
- map[1 + i][1 + j] = 1;
- }
- }
- std::queue<Point> points;
- points.emplace(r + 1, r);
- points.emplace(r - 1, r);
- points.emplace(r, r + 1);
- points.emplace(r, r - 1);
- for (int color = 2; !points.empty(); ++color) {
- validatePoints(points, color);
- }
- for (int i = 0; i < map.size(); ++i) {
- for (int j = 0; j < map.size(); ++j) {
- std::cout << map[i][j] << ' ';
- }
- std::cout << '\n';
- }
- std::ofstream output("output.txt");
- if (!output.good()) {
- std::cout << "File error: output.txt\n";
- return 1;
- }
- if (map[m][m] == 0) {
- output << "No";
- } else {
- output << map[m][m] - 1;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement