23 / 23 / 13
Регистрация: 12.10.2018
Сообщений: 240
1

Определить, существует ли маршрут (вариант обхода графа), удовлетворяющий заданным критериям

27.02.2019, 19:31. Показов 3494. Ответов 25
Метки нет (Все метки)

Задано прямоугольное поле n × m, в одной из ячеек в момент времени 1 появляется турист. Каждую секунду он переходит в одну из 4-х соседних ячеек, в которой он еще не был, а при переходе в новую клетку девайс туриста старательно отсылает вам номер секунды, на которой он оказался в клетке. Турист никогда надолго не задерживается, а после перехода мгновенно выбирает следующую точку, и за одну секунду оказывается в ней. После того, как турист обходил все поле, data - центр собрал для вас всю информацию в виде таблицы a размером n × m, где aij - время, когда турист здесь появился.
Нужно определить, существует ли такой маршрут, что обходит всю таблицу, обходит все клетки по одному разу и для каждой ячейки делает это в момент времени aij.

Входные данные:
В первой строке входного файла содержится два целых числа n, m (1 ≤ n, m ≤ 1000) - размеры таблицы. В следующих n строках содержится по m целых чисел в каждой строке aij (1 ≤ aij ≤ 10^6) - моменты времени, в которые нужно появляться в клетке.
Исходные данные:
Выведите «YES», если существует такой маршрут, и «NO», если не существует.

Примеры:

Кликните здесь для просмотра всего текста
Ввод
3 3
1 2 3
6 5 4
7 8 9
Вывод
YES

Ввод
2 2
1 2
3 4
Вывод
NO

Ввод
3 4
1 2 9 10
4 3 8 11
5 6 7 12
Вывод
YES
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
27.02.2019, 19:31
Ответы с готовыми решениями:

Найти маршрут, включающий максимальное количество городов и удовлетворяющий вышеназванными условиям
Вы победили в соревновании, организованном Канадскими авиалиния-ми. Приз – бесплатное путешествие...

Методом обхода в глубину определить число компонент связности и цикломатическое число графа
Методом обхода в глубину определить число компонент связности и цикломатическое число графа –...

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

Определить, существует ли треугольник по двум заданным углам
Даны два угла треугольника (в градусах). Определить существует ли такой треугольник. Если да, то...

25
Мозгоправ
1735 / 1029 / 468
Регистрация: 01.10.2018
Сообщений: 2,138
Записей в блоге: 2
03.03.2019, 16:21 21
Цитата Сообщение от Вадим Тукаев Посмотреть сообщение
Потому что эти входные данные не соответствуют условию задачи.
Соответствуют.
Цитата Сообщение от aassii Посмотреть сообщение
Входные данные:
В первой строке входного файла содержится два целых числа n, m (1 ≤ n, m ≤ 1000) - размеры таблицы. В следующих n строках содержится по m целых чисел в каждой строке aij (1 ≤ aij ≤ 10^6) - моменты времени, в которые нужно появляться в клетке.
Ни где не сказано, что моменты времени числа последовательные. Даны только общие ограничения.

aassii, а можете показать скрин отчёта по моему первому варианту?
0
23 / 23 / 13
Регистрация: 12.10.2018
Сообщений: 240
03.03.2019, 16:28  [ТС] 22
L0M, Вадим Тукаев, всем спасибо за помощь! Все ваши три программы прошли все тесты только после отключения синхронизации между потоками ввода вывода С и С++.
0
Мозгоправ
1735 / 1029 / 468
Регистрация: 01.10.2018
Сообщений: 2,138
Записей в блоге: 2
03.03.2019, 17:47 23
aassii, а по скорости выполнения доступна статистика?
Из трёх вариантов какой самый быстрый?
0
23 / 23 / 13
Регистрация: 12.10.2018
Сообщений: 240
03.03.2019, 18:21  [ТС] 24
Результаты:
Вложения
Тип файла: rar Time.rar (163.4 Кб, 4 просмотров)
0
23 / 23 / 13
Регистрация: 12.10.2018
Сообщений: 240
03.03.2019, 18:40  [ТС] 25
Это результаты работы программ после отключения синхронизации между потоками ввода вывода С и С++.
0
Мозгоправ
1735 / 1029 / 468
Регистрация: 01.10.2018
Сообщений: 2,138
Записей в блоге: 2
03.03.2019, 19:04 26
Спасибо за результаты.
Ну да, примерно как и ожидалось.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
03.03.2019, 19:04
Помогаю со студенческими работами здесь

Определить существует ли треугольник по заданным трем сторонам
1.Определите существует ли треугольник по заданным трем сторонам. Результат записать в файл

По заданным трём сторонам определить, существует ли треугольник, и, если да, то какой
Даны три стороны треугольника, узнать существует ли он, и если да то...

Определить все варианты остовных подграфов полного графа с заданным количеством ребер
Всем привет! Помогите, пожалуйста:) Не могу никак понять алгоритм действий для выполнения задания...

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


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
26
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru