|
Задача про игру «Сапёр»
На поле для игры в «Сапёр» клеточки с минами обозначаются символом «*», а в каждой пустой клеточке записано число от 0 до 8, равное количеству мин в 8 клетках, соседних с данной.
Дан список мин на поле. Постройте по данному списку изображение поля.
Решение
Заведём двумерный массив для хранения поля игры. В клетки, где стоят мины, будем записывать −1. В остальных клетках будем хранить, сколько мин являются соседями данной клетки. Заметим, что у клеток, которые находятся на краю поля, количество соседей меньше 8 (часть соседей находится вне поля). Поэтому для удобства мы увеличим размер поля с каждой из четырёх сторон на одну клетку. Теперь мы гарантируем, что у каждой клетки на изначальном поле ровно 8 соседей, и никакая операция просмотра соседней клетки не приведёт нас к выходу за пределы поля.
Упростим перебор всех соседей данной клетки. Для этого заведём массивы di и dj, каждый из которых будет иметь размер 8 и хранить сдвиг каждого соседа по вертикали и горизонтали соответственно.
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n, m, k;
cin >> n >> m >> k;
vector<vector<int> > t(n + 2, vector<int> (m + 2, 0));
for (int i = 0; i < k; ++i){
int mi, mj;
cin >> mi >> mj;
t[mi][mj] = -1;
}
vector<int> di = {-1, -1, -1, 0, 0, 1, 1, 1};
vector<int> dj = {-1, 0, 1, -1, 1, -1, 0, 1};
for (int i = 1; i < t.size() - 1; ++i){
for (int j = 1; j < t[i].size() - 1; ++j){
if (t[i][j] == -1){
for (int k = 0; k < 8; ++k){
int ni = i + di[k];
int nj = j + dj[k];
if (t[ni][nj] != -1)
++t[ni][nj];
}
}
}
}
for (int i = 1; i < t.size() - 1; ++i){
for (int j = 1; j < t[i].size() - 1; ++j){
if (t[i][j] == -1){
cout << "*";
}
else if (t[i][j] == 0){
cout << ".";
}
else{
cout << t[i][j];
}
}
cout << endl;
}
return 0;
}
|