Задача

В международной политике важным понятием является граница между государствами. Нечеткое понимание сторонами того, где проходит граница, может привести к международным конфликтам и даже войнам. В этой задаче ситуация обстоит несколько проще, так как у двух рассматриваемых в задаче государств есть четкое понимание, какая территория принадлежит какому из них. Территория, занимаемая этими двумя государствами, представляет собой прямоугольник размером [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

Код

#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;
}

#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

Related Images:

Задача

В некоторой древней стране жили-были братья. Сколько их было, нам точно не известно, но в исторических источниках упоминается, что их точно было не менее трех. С течением времени у них появились дети и разбрелись они по миру, причем как и их родители, каждый построил свой город. Опять же с течением времени количество родственников начало стремительно возрастать и решили они между некоторыми городами построить дороги, а некоторые из них, уже до этого успели построить и объездные дороги вокруг своего города. В рукописях упоминается, что количество городов в той стране не превышало $8000$. Кроме того, в тех же рукописях содержались схематические карты, которые показывали наличие дорог между городами, или объездной дороги вокруг города. Карты имели вид квадратных матриц, в которых цифра $1$ указывала на наличие дороги между городами, или вокруг города, или $0$ в случае отсутствия таковой.

Изучите древние рукописи и дайте ответ на вопрос: а сколько же дорог было построено между городами?

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

В первой строке задано количество городов $n$, а в последующих $n$ строках через пробел задано по $n$ чисел, которые указывают на наличие или отсутствие соответствующей дороги.

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

Количество построенных между городами дорог.

Код программы

#include <iostream>
#include <stdio.h>
using namespace std;

int main() {
    int n, k = 0;
    cin >> n;     cin.ignore(); //считываем n и игнорируем символ перевода строки
    const int N = 2 * n + 1;
    char c[N];
    for(int i = 0; i < n; i++) {
        fgets(c, N, stdin); //считываем строку
        for(int j = 0; j < i; j++) 
            k = k + c[j << 1] - 48; //переводим символ из ascii кода в число
    }
    cout << k;

    return 0;
}

#include <iostream>

#include <stdio.h>

using namespace std;

int main() {

int n, k = 0;

cin >> n; cin.ignore(); //считываем n и игнорируем символ перевода строки

const int N = 2 * n + 1;

char c[N];

for(int i = 0; i < n; i++) {

fgets(c, N, stdin); //считываем строку

for(int j = 0; j < i; j++)

k = k + c[j << 1] - 48; //переводим символ из ascii кода в число

}

cout << k;

return 0;

}

Решение задачи

Задача не сложная – посчитать количество ребер в графе, заданном матрицей смежности.

Сложность задачи состоит в ограничениях по времени – не более одной секунды (ощутимо при больших значенях $n$, так как $3 ≤ n ≤ 8000$). Поэтому приходится быстро вводить данные в больших количествах. Для этого используем символьный массив и любую функцию, которая читает целую строку чисел (в моем случае – fgets()), которая читает строку, пока не встретит символ перевода строки – '\n'.

Далее по одному переводим символы в числа и суммируем их в переменной k, после чего выводим.

Входные данные	Выходные данные
5 1 1 1 1 0 1 0 1 0 1 1 1 1 0 1 1 0 0 0 1 0 1 1 1 1	7
4 0 1 0 1 1 1 0 1 0 0 1 0 1 1 0 0	3
3 1 1 0 1 0 1 0 1 0	2
3 0 1 1 1 0 1 1 1 0	3
3 1 0 0 0 1 0 0 0 1	0

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

Tag Archives: символьный массив

e-olymp 2507. Граница

Задача

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

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

Тесты

Код

Решение

Related Images:

e-olymp 610. Древняя рукопись

Задача

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

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

Тесты

Код программы

Решение задачи

Ссылки

Related Images: