Confine (Editoriale)

Inseriamo l'area rettangolare in un array di caratteri. Consideriamo l'elemento $s[i][j]$. Se differisce da s[i + 1][j], significa che tra di essi passa un confine di lunghezza $1$ (cioè sotto $s[i][j]$ c'è un confine).

Analogamente, se $s[i][j]$ differisce da s[i][j + 1], tra di essi passa anch'esso un confine di lunghezza $1$ (a destra di $s[i][j]$ c'è un confine).

Resta da esaminare tutte le posizioni $(i,j)$ e per ciascuna contare il numero di confini inferiori e destri.

Esempio

Il confine tra gli stati è mostrato in rosso. La sua lunghezza è pari a $13$.

Implementazione dell'algoritmo

Memorizziamo i territori degli stati nell'array $s$.

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

Leggiamo i dati di input.

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

Calcoliamo la lunghezza dei confini verticali.

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

Calcoliamo la lunghezza dei confini orizzontali.

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

Stampiamo la risposta.

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

Implementazione dell'algoritmo – string

Memorizziamo i territori degli stati nell'array $s$.

vector<string> s;

Leggiamo i dati di input.

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

Calcoliamo la lunghezza dei confini verticali.

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

Calcoliamo la lunghezza dei confini orizzontali.

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

Stampiamo la risposta.

cout << res << endl;