Вася очень любит играть в известную игру «Сапер» («Minesweeper»). Игра проходит на поле размером N×M клеток, где N — количество строк, а M — количество столбцов. В K клетках поля установлены мины, а в остальных клетках записано либо число от 1 до 8 — количество мин в соседних клетках, либо ничего (если в соседних клетках мин нет). Соседними считаются клетки, имеющие хотя бы одну общую сторону. Изначально все клетки поля закрыты. Игрок может открыть любую клетку. Если в ней окажется мина — он проигрывает, иначе ему показывается число, стоящее в этой клетке, и игра продолжается. Цель игры — открыть все клетки, в которых нет мин.
У Васи есть идея создать свои собственные карты для игры, так как стандартные ему кажутся скучными. Он выбирает размеры поля N и M, а также количество мин K и их координаты. Ваша задача — по заданным значениям N, M, K и координатам мин восстановить полную карту.
Первая строка входного файла INPUT.TXT содержит три числа: N, M и K (1 ≤ N ≤ 200, 1 ≤ M ≤ 200, 0 ≤ K ≤ N×M). Следующие K строк содержат по два числа, определяющих координаты мин. Первое число в каждой строке — номер строки клетки, второе число — номер столбца. Левая верхняя клетка имеет координаты (1,1), правая нижняя — (N,M).
Выходной файл OUTPUT.TXT должен содержать N строк по M символов. j-й символ i-й строки должен быть:
Объяснение кода
Приведенный ниже код решает задачу восстановления полной карты «Сапер» по заданным размерам поля и координатам мин.
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
|
#include <iostream> #include <fstream> #include <vector> using namespace std; // Функция для проверки, находится ли точка внутри границ bool isInside(int x, int y, int n, int m) { return (x >= 0 && x < n && y >= 0 && y < m); } int main() { ifstream inputFile("INPUT.TXT"); ofstream outputFile("OUTPUT.TXT"); if (!inputFile.is_open()) { cerr << "Не удалось открыть входной файл!" << endl; return 1; } int n, m, k; inputFile >> n >> m >> k; // Инициализируем поле с нулями vector<vector<int>> field(n, vector<int>(m, 0)); // Чтение координат мин и установка их на поле for (int i = 0; i < k; ++i) { int x, y; inputFile >> x >> y; --x; // Индексы на единицу меньше, потому что в задаче они начинаются с 1 --y; field[x][y] = -1; // Используем -1 для обозначения мин } inputFile.close(); // Массивы для движения в восьми направлениях int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1}; int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1}; // Обновление поля вокруг каждой мины for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (field[i][j] == -1) { // Если это мина for (int d = 0; d < 8; ++d) { int ni = i + dx[d]; int nj = j + dy[d]; if (isInside(ni, nj, n, m) && field[ni][nj] != -1) { field[ni][nj]++; } } } } } // Вывод обновленного поля for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (field[i][j] == -1) { outputFile << '*'; } else if (field[i][j] == 0) { outputFile << '.'; } else { outputFile << field[i][j]; } } outputFile << endl; } outputFile.close(); return 0; } |
Объяснение кода
Программа состоит из нескольких частей, каждая из которых выполняет определенную функцию для решения задачи.
Заголовки и пространство имен
|
#include <iostream> #include <fstream> #include <vector> using namespace std; |
Здесь подключаются необходимые заголовочные файлы. <iostream>
и <fstream>
используются для ввода-вывода, <vector>
— для работы с динамическими массивами.
Функция проверки границ
|
bool isInside(int x, int y, int n, int m) { return (x >= 0 && x < n && y >= 0 && y < m); } |
Эта функция проверяет, находится ли заданная точка (x, y)
внутри границ поля размером n × m
. Возвращает true
, если точка внутри границ, иначе false
.
Основная функция
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
|
int main() { ifstream inputFile("INPUT.TXT"); ofstream outputFile("OUTPUT.TXT"); if (!inputFile.is_open()) { cerr << "Не удалось открыть входной файл!" << endl; return 1; } int n, m, k; inputFile >> n >> m >> k; // Инициализируем поле с нулями vector<vector<int>> field(n, vector<int>(m, 0)); // Чтение координат мин и установка их на поле for (int i = 0; i < k; ++i) { int x, y; inputFile >> x >> y; --x; // Индексы на единицу меньше, потому что в задаче они начинаются с 1 --y; field[x][y] = -1; // Используем -1 для обозначения мин } inputFile.close(); // Массивы для движения в восьми направлениях int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1}; int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1}; // Обновление поля вокруг каждой мины for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (field[i][j] == -1) { // Если это мина for (int d = 0; d < 8; ++d) { int ni = i + dx[d]; int nj = j + dy[d]; if (isInside(ni, nj, n, m) && field[ni][nj] != -1) { field[ni][nj]++; } } } } } // Вывод обновленного поля for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (field[i][j] == -1) { outputFile << '*'; } else if (field[i][j] == 0) { outputFile << '.'; } else { outputFile << field[i][j]; } } outputFile << endl; } outputFile.close(); return 0; } |
Основная функция программы выполняет следующие действия:
- Открывает входной файл для чтения и выходной файл для записи.
- Считывает размеры игрового поля
n
и m
, а также количество мин k
.
- Инициализирует поле нулями.
- Читает координаты мин и отмечает их на поле, используя значение
-1
.
- Обновляет значения вокруг каждой мины, увеличивая счётчик мин в соседних клетках.
- Выводит окончательное поле в выходной файл, заменяя
-1
на *
, нули на точки .
, а остальные числа оставляет как есть.