Задача
Дана прямоугольная доска [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 34 35 36 37 |
import java.io.BufferedReader; import java.io.InputStreamReader; class Main { public static void main (String[] args) throws java.lang.Exception { BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); String[] params1 = bufferedReader.readLine().split(" "); int x, y; x = Integer.parseInt(params1[0]); y = Integer.parseInt(params1[1]); boolean mas[][] = new boolean[x][y]; for (int i = 0; i < x; ++i){ String[] params2 = bufferedReader.readLine().split(" "); for (int j = 0; j < y; ++j){ char buff; buff = params2[0].charAt(j); if (buff == '.') mas[i][j] = true; else mas[i][j] = false; } System.out.print("\n"); } 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; } } } System.out.print(sum); } } |
Решение
Для решения данной задачи создаем динамический массив типа [latex]bool[/latex] [latex]x[/latex] на [latex]y[/latex]. Заполняем соответствующий элемент значением [latex]true[/latex], когда вводится «.» и значением [latex]false[/latex] в противном случае. Далее увеличиваем значение количества уголков на , если существуют не пустые клетки.