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