Кордон (Розбір)

Занесемо прямокутну область у символьний масив. Розглянемо елемент $s[i][j]$. Якщо він відрізняється від s[i + 1][j], значить, між ними проходить границя довжиною $1$ (тобто знизу від $s[i][j]$ є границя).

Аналогічно якщо $s[i][j]$ відрізняється від s[i][j + 1], між ними також проходить границя довжиною $1$ (справа від $s[i][j]$ є границя).

Залишається перебрати всі позиції $(i,j)$ і для кожної порахувати кількість нижніх та правих границь.

Приклад

Границя між державами показана червоним кольором. Її довжина дорівнює $13$.

Реалізація алгоритму

Території держав зберігаємо в масиві $s$.

#define MAX 110
char s[MAX][MAX];

Читаємо вхідні дані.

scanf("%d %d\n", &w, &h);
for (i = 0; i < h; i++)
  gets(s[i]);

Рахуємо довжину вертикальних границь.

for (i = 0; i < h; i++)
for (j = 0; j < w - 1; j++)
  if (s[i][j] != s[i][j + 1]) res++;

Рахуємо довжину горизонтальних границь.

for (i = 0; i < h - 1; i++)
for (j = 0; j < w; j++)
  if (s[i][j] != s[i + 1][j]) res++;

Виводимо відповідь.

printf("%d\n", res);

Реалізація алгоритму – string

Території держав зберігаємо в масиві $s$.

vector<string> s;

Читаємо вхідні дані.

cin >> w >> h;
s.resize(h);
for (i = 0; i < h; i++)
  cin >> s[i];

Рахуємо довжину вертикальних границь.

for(i = 0; i < h; i++)
for(j = 0; j < w - 1; j++)
  if (s[i][j] != s[i][j+1]) res++;

Рахуємо довжину горизонтальних границь.

for(i = 0; i < h - 1; i++)
for(j = 0; j < w; j++)
  if (s[i][j] != s[i+1][j]) res++;

Виводимо відповідь.

cout << res << endl;