Задача
В международной политике важным понятием является граница между государствами. Нечеткое понимание сторонами того, где проходит граница, может привести к международным конфликтам и даже войнам. В этой задаче ситуация обстоит несколько проще, так как у двух рассматриваемых в задаче государств есть четкое понимание, какая территория принадлежит какому из них. Территория, занимаемая этими двумя государствами, представляет собой прямоугольник размером [latex]h[/latex] на [latex]w[/latex] километров, разбитый на квадраты со стороной в один километр. Каждый из этих квадратов полностью принадлежит либо первому государству, либо второму. Необходимо определить длину границы между двумя государствами. Сторона единичного квадрата считается принадлежащей границе, если по одну сторону от нее лежит квадрат, принадлежащий первому государству, а по другую — принадлежащий второму.
Входные данные
Первая строка содержит два целых числа: [latex]w[/latex] и [latex]h \left(1 \leqslant w, h \leqslant 100\right)[/latex] — размеры прямоугольника в километрах. Далее следуют [latex]h[/latex] строк, описывающих территорию. Каждая из них содержит [latex]w[/latex] символов. Если символ равен [latex]A[/latex], то соответствующий единичный квадрат принадлежит первому государству, а если он равен [latex]B[/latex], то второму. Гарантируется, что каждому государству принадлежит хотя бы один квадрат. Территории каждого из государств представляют собой связные области.
Выходные данные
Выведите одно целое число — длину границы между государствами в километрах.
Тесты
| # | ВХОДНЫЕ ДАННЫЕ | ВЫХОДНЫЕ ДАННЫЕ |
|---|---|---|
| 1 | 5 6 AAABB ABBBB AAABB AAAAB AAAAB AABBB |
13 |
| 2 | 4 3 AAAA AAAA AAAB |
2 |
| 3 | 5 9 BBBBB ABBBB AABBB AAABB AAAAB AAABB AABBB ABBBB BBBBB |
15 |
| 4 | 2 1 AB |
1 |
| 5 | 6 5 AABBBB BBBBBB BBBAAA AAAAAA AAAAAA |
10 |
Код
|
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 |
#include <iostream> using namespace std; int main() { int w, h, res = 0; cin >> w >> h; char **x = new char *[h]; for (int i = 0; i < h; i++) x[i] = new char[w]; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { cin >> x[i][j]; } } for (int i = 0; i < h; i++) { for (int j = 0; j < w - 1; j++) { if (x[i][j] != x[i][j + 1]) res++; } } for (int i = 0; i < h - 1; i++) { for (int j = 0; j < w; j++) { if (x[i][j] != x[i + 1][j]) res++; } } cout << res << endl; return 0; } |
Решение
Занесем прямоугольную область в многомерный массив символов. Рассмотрим символ x[i][j]. Если он не совпадает с x[i + 1][j], то между ними имеется граница длины 1 (снизу от x[i][j] проходит граница). Аналогично, если x[i][j] не совпадает с x[i][j + 1], то между ними имеется граница длины 1 (справа от x[i][j] проходит граница). Остается перебрать все символы и подсчитать для них количество нижних и правых границ.
Запустить код (ideone) можно здесь
Задача на E-olymp