Решение задачи третьего квалификационного раунда Russian Code Cup (2011 год)


Задача «B». Граница (все задачи третьего квалификационного раунда)

Ограничение по времени: 2 секунды.
Ограничение по памяти: 256 мегабайт.

В международной политике важным понятием является граница между государствами. Нечеткое понимание сторонами того, где проходит граница, может привести к международным конфликтам и даже войнам.

В этой задаче ситуация обстоит несколько проще, так как у двух рассматриваемых в задаче государств есть четкое понимание, какая территория принадлежит какому из них.

Территория, занимаемая этими двумя государствами, представляет собой прямоугольник размером hна w километров, разбитый на квадраты со стороной в один километр. Каждый из этих квадратов полностью принадлежит либо первому государству, либо второму.

Необходимо определить длину границы между двумя государствами. Сторона единичного квадрата считается принадлежащей границе, если по одну сторону от нее лежит квадрат, принадлежащий первому государству, а по другую — принадлежащий второму.

Формат входных данных

Первая строка содержит два целых числа: w и h — размеры прямоугольника в километрах (1 ≤ w, h ≤ 100). Далее следуют h строк, описывающих территорию. Каждая из них содержит w символов. Если символ равен A, то соответствующий единичный квадрат принадлежит первому государству, а если он равен B, то второму. Гарантируется, что каждому государству принадлежит хотя бы один квадрат.

Территории каждого из государств представляют собой связные области.

Формат выходных данных

Выведите одно целое число — длину границы между государствами в километрах.

Примеры

Входные данные

5 6
AAABB
ABBBB
AAABB
AAAAB
AAAAB
AABBB

Выходные данные
13

Мое решение

using System;

class StateBorder
{
  enum State
  {
    A, B
  }

  static void Main()
  {
    int i, j, h, w;
    int len = 0;
    char [] delim = new char[]{' '};
    char[] cells;

    string[] numbers = Console.ReadLine().Split(delim);
    w = Convert.ToInt32(numbers[0]);
    h = Convert.ToInt32(numbers[1]);

    int LastRow = h - 1;
    int LastCol = w - 1;

    State[,] cell = new State[h, w];

    for (i = 0; i < h; i++)
    {
      cells = Console.ReadLine().ToCharArray();
      for(j = 0; j < w; j++)
      {
        cell[i, j] = (State)Enum.Parse(typeof(State), cells[j].ToString());
        if (j > 0)
        {
          if (cell[i, j] != cell[i, j - 1])
          {
            len++;
          }
        }
        if (i > 0)
        {
          if (cell[i, j] != cell[i - 1, j])
          {
            len++;
          }
        }
      }
    }
    Console.WriteLine(len);
  }
}
Реклама
Запись опубликована в рубрике программирование с метками , . Добавьте в закладки постоянную ссылку.

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s