C/C++

Задача по программированию. Решить на Python или C++

В некоторых случаях проверить корректность работы программы гораздо сложнее, чем написать ее. Сейчас у вас будет шанс в этом убедиться. От вас требуется написать программу для проверки корректности ответа второй задачи этой попытки. Напомним ее условие. Имеется парк в виде шестиугольника с 12 аллеями, которые обозначены заглавными символами латиницы. В парке есть только один вход у перекрестка аллей "A", "F", "G". Схема парка приведена ниже.  Требуется проверить  корректность составленного маршрута движения по этому парку. Маршрут представляется, как последовательность  символов, представляющих аллеи в том порядке, в котором они были пройдены. Маршрут движения считается корректным если выполняются следующие требования.

Описание маршрута содержит только символы от "A" до "L".
Маршрут начинается и заканчивается у входа в парк.
Запрещено разворачиваться на 180 градусов. В частности, это означает, что начав движение с одного конца аллеи, вы обязательно дойдете до другого ее конца, причем на перекрестке вы должны будете перейти на другую аллею.
На вход вашей программе будет подано несколько описаний маршрутов. Ваша программа должна будет определить, какие из них удовлетворяют указанным требованиям.


Формат входных данных
На вход в первой строке подается одно натуральное число nn — количество проверяемых маршрутов, 1\le n \le 401≤n≤40. Далее в nn строках записаны сами маршруты. Описание каждого маршрута состоит из последовательности заглавных символов латиницы. Каждое описание не пустое и содержит не более 100 символов.

Формат выходных данных
Программа должна вывести строку из nn нулей и единиц. Единица на ii-той позиции означает, что маршрут с номером ii является корректным. В противном случае в этой позиции должен быть записан ноль.

Методика проверки
Программа проверяется на 8 тестах. Прохождение каждого теста оценивается в 4 балла. Тест из условия задачи при проверке не используется.

Sample Input 1:
6
ABCDKHA
FMG
ABBA
ABCEF
BCDEF
ABCDK

Sample Output 1:
100000

Пояснение к примеру
Первый маршрут является корректным.

Второй маршрут содержит недопустимое обозначение аллеи.

В третьем маршруте происходит разворот на 180 градусов.

Четвертый маршрут не является связным. После третьего шага он приходит к перекрестку "C", "D", "J" и с него нельзя попасть на аллею "E".

Пятый маршрут начинается не у входа.

Шестой маршрут заканчивается не у входа.
Владислав Бочкарев
Владислав Бочкарев
160 
 #include  

#include  

#include  

#include  

using namespace std; 

class Route { 

protected: 

    bool static exist(const string& route) { 

        const size_t length = route.length(); 

        if (length < 3) return false;

        if (input.find(route.front()) == string::npos) return false;

        if (input.find(route.back()) == string::npos) return false;

        for (size_t i = 0, j = 1; j < length; ++i, ++j) { 

            auto a = pattern.find(route[i]); 

            if (a == string::npos) return false; 

            auto b = pattern.find(route[j]); 

            if (b == string::npos) return false; 

            if (matrix[a][b] == 0) return false;

            if (j > 1 && route[j] == route[j - 2]) return false;

        } 

        return true; 

    } 

private:

    inline static const string input{ "AFG" };

    inline static const string pattern{ "ABCDEFGHIJKL" }; 

    inline static const int matrix[12][12]{ 

        { 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0 }, 

        { 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0 }, 

        { 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0 }, 

        { 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0 }, 

        { 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1 }, 

        { 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1 }, 

        { 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1 }, 

        { 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1 }, 

        { 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1 }, 

        { 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1 }, 

        { 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1 }, 

        { 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0 } 

    }; 

}; 

template 

class Routes : public Route { 

public: 

    void add(const string& route) { 

        routes.push_back(route); 

    } 

    string get()const { 

        bitset box; 

        size_t pos = routes.size() - 1; 

        for (const auto& route : routes) { 

            if (exist(route)) { 

                box.set(pos); 

            } 

        } 

        const auto s = box.to_string(); 

        const auto n = Size - routes.size(); 

        return string{ s.begin() + n, s.end() }; 

    } 

private: 

    vector routes; 

}; 

int main() { 

    size_t quantity; 

    cin >> quantity; 

    string route; 

    Routes routes; 

    for (size_t i = 0; i < quantity; ++i) { 

        cin >> route; 

        routes.add(route); 

    } 

    auto box = routes.get(); 

    cout
Кирилл Якубинский
Кирилл Якубинский
85 948
Лучший ответ
Кирилл Якубинский Я думаю, что моё решение не совсем верное, так как при маршруте ABHGA программа считает маршрут валидным, но по факту с B на H можно попасть только развернувшись где-то на полпути назад, а развороты на 180 градусов запрещены.
Кирилл Якубинский Метод exist следует переписать следующим образом:
 bool static exist(const string& route) { 

    const size_t length = route.length(); 

    if (length < 3) return false; 

    if (entry.find(route.front()) == string::npos) return false; 

    if (entry.find(route.back()) == string::npos) return false; 

    for (size_t i = 0, j = 1; j < length; ++i, ++j) { 

        auto a = pattern.find(route[i]); 

        if (a == string::npos) return false; 

        auto b = pattern.find(route[j]); 

        if (b == string::npos) return false; 

        if (matrix[a][b] == 0) return false; 

        if (j > 1) { 

            if (route[j] == route[j - 2]) return false; 

            auto c = pattern.find(route[i - 1]); 

            if (matrix[c][b] == 1) return false; 

        } 

    } 

    return true; 

}
Кирилл Якубинский И метод статической свойство input переименовать в entry
 inline static const string entry{ "AFG" };
Дима Багинский респект чуваку
Это дипломная работа цена $5000
Роман Романов
Роман Романов
61 233 
 #include 

#include 

using namespace std;



int find_next(int skip , char Ch, vector& paths)

{

	for (int i = 0; i < paths.size(); i++)

	{

		if (i == skip) continue;

		if (paths[i].find(Ch) != string::npos) return i;

	}

	return -1;

}

 

char searcher(string str)

{

	static vector  paths{ "FGA","AHB","BIC","CJD","DKE","ELF","GHIJKL" };

	for (int i = 1; i < str.size(); i++) if (str[i] == str[i - 1]) return '0';

	int tmp = 0;

	for (auto& i : str)

	{

		if (paths[tmp].find(i) != string::npos) { tmp = find_next(tmp, i, paths); if (tmp == -1) return '0'; }

	}

	return tmp==0?'1':'0';

}

 

int main()

{

	int n;

	string str, result;

	cin >> n;

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

	{

		cin >> str;

		result.push_back(searcher(str));

	}

	cout
SV
Slavik Vakyla
51 416
Vitali Loginov спасибо!!!
Cемён Бельков через какую прогу?
Александр Цапаев Спасибо тебе! Ты красавчик !!!
Василий Баланичев А есть решение к этой задаче через python 3?
Пишет runtime error
Семен Мартынов
Семен Мартынов
106

Похожие вопросы