Задача
Дана прямоугольная доска [latex]M×N[/latex], некоторые клетки в которой вырезаны. Сколькими способами можно поставить на неё «уголок» из трёх клеток так, чтобы все три клетки уголка находились внутри доски и не были вырезаны?
Входные данные
В первой строке входного файла даны два числа [latex]M[/latex] и [latex]N[/latex] [latex](1 \leq M, N \leq 100)[/latex], разделённые пробелом. В следующих [latex]M[/latex] строках содержится по [latex]N[/latex] символов в каждой; [latex]i[/latex]-ый символ [latex]j[/latex]-ой из этих строк равен ‘X’ (большая буква икс), если клетка вырезана, и ‘.’ (точка) в противном случае.
Выходные данные
Выведите одно число — сколько существует способов поставить уголок на данную доску.
Тесты
Входные данные | Выходные данные |
---|---|
2 2 .. .. |
4 |
2 3 ..X .X. |
1 |
5 4 …. X.XX …. X..X ..XX |
12 |
Код программы
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 |
#include <iostream> using namespace std; int main() { int x, y; cin >> x >> y; bool **mas = new bool*[x]; for (int i = 0; i < x; ++i){ mas[i] = new bool[y]; } for (int i = 0; i < x; ++i){ for (int j = 0; j < y; ++j){ char buff; cin >> buff; if (buff == '.') mas[i][j] = true; else mas[i][j] = false; } cout << endl; } int sum = 0; for (int i = 0; i < x; ++i){ for (int j = 0; j < y; ++j){ if (mas[i][j]){ if (i - 1 >= 0 && j - 1 >= 0) if (mas[i - 1][j] && mas[i][j - 1]) ++sum; if (i - 1 >= 0 && j + 1 < y) if (mas[i - 1][j] && mas[i][j + 1]) ++sum; if (i + 1 < x && j + 1 < y) if (mas[i + 1][j] && mas[i][j + 1]) ++sum; if (i + 1 < x && j - 1 >= 0) if (mas[i + 1][j] && mas[i][j - 1]) ++sum; } } } cout << sum; return 0; } |
Решение
Для решения данной задачи создаем динамический массив типа bool x на y. Заполняем соответствующий элемент значением true, когда вводится «.» и значением false в противном случае. Далее увеличиваем значение количества уголков на $1$, если существуют не пустые клетки.
2 thoughts on “e-olymp 2812. Уголок”