Sərhəd (Həll təhlili)

Düzbucaqlı ərazini simvol massivinə yerləşdirək. $s[i][j]$ elementinə baxaq. Əgər o, s[i + 1][j] elementindən fərqlənirsə, deməli, onların arasında uzunluğu $1$ olan sərhəd keçir (yəni $s[i][j]$-in altında sərhəd var).

Oxşar şəkildə, əgər $s[i][j]$ elementi s[i][j + 1] elementindən fərqlənirsə, onların arasında da uzunluğu $1$ olan sərhəd keçir ($s[i][j]$-in sağında sərhəd var).

Qalan iş bütün $(i,j)$ mövqelərini gəzmək və hər biri üçün alt və sağ sərhədlərin sayını hesablamaqdır.

Nümunə

Dövlətlər arasındakı sərhəd qırmızı rənglə göstərilib. Onun uzunluğu $13$-ə bərabərdir.

Alqoritmin realizasiyası

Dövlətlərin ərazilərini $s$ massivində saxlayırıq.

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

Giriş məlumatlarını oxuyuruq.

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

Şaquli sərhədlərin uzunluğunu hesablayırıq.

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

Üfüqi sərhədlərin uzunluğunu hesablayırıq.

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

Cavabı çıxarırıq.

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

Alqoritmin realizasiyası – string

Dövlətlərin ərazilərini $s$ massivində saxlayırıq.

vector<string> s;

Giriş məlumatlarını oxuyuruq.

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

Şaquli sərhədlərin uzunluğunu hesablayırıq.

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

Üfüqi sərhədlərin uzunluğunu hesablayırıq.

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

Cavabı çıxarırıq.

cout << res << endl;