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

@aassii · Регистрация: 12.10.2018

Студворк — интернет-сервис помощи студентам

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

Входные данные:
В первой строке входного файла содержится два целых числа n, m (1 ≤ n, m ≤ 1000) - размеры таблицы. В следующих n строках содержится по m целых чисел в каждой строке aij (1 ≤ a_ij ≤ 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

@L0M · 03.03.2019, 16:21

Сообщение от Вадим Тукаев

Потому что эти входные данные не соответствуют условию задачи.

Соответствуют.

Сообщение от aassii

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

Ни где не сказано, что моменты времени числа последовательные. Даны только общие ограничения.

aassii, а можете показать скрин отчёта по моему первому варианту?

@aassii · 03.03.2019, 16:28 **[ТС]**

L0M, Вадим Тукаев, всем спасибо за помощь! Все ваши три программы прошли все тесты только после отключения синхронизации между потоками ввода вывода С и С++.

@L0M · 03.03.2019, 17:47

aassii, а по скорости выполнения доступна статистика?
Из трёх вариантов какой самый быстрый?

@aassii · 03.03.2019, 18:21 **[ТС]**

Результаты:

@aassii · 03.03.2019, 18:40 **[ТС]**

Это результаты работы программ после отключения синхронизации между потоками ввода вывода С и С++.

@L0M · 03.03.2019, 19:04

Спасибо за результаты.
Ну да, примерно как и ожидалось.

Новые блоги и статьи Все статьи Все блоги /
После закрытия оутлука продолжает висеть процесс в диспетчере задач Maks 27.10.2026 С недавнего времени в продакшене возникла проблема: при закрытии оутлука в диспетчере задач продолжал висеть процесс outlook. exe. Проблема возникла после установки MS Office 2021 LTSC на машинах, под. . .	Baragoz - DPS/HPS бот для WoW 3.3.5a, многоязычный AmbA 26.10.2026 Хотите ещё ботов? У меня есть один! А я пока отдохну от него. https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=12062&stc=1&d=1793007952 Инструкция внутри. https:/ / youtu. be/ VpfFZSUDGnQ. . .	Особенности gif сгенерированных в Си russiannick 21.10.2026 Рассмотрим генерацию gif файлов, которые в Си имеют свои особенности. Gif представляет собой графический формат популярный в интернете. Посмотрим на палитру. Gif файл сгенерированный в си отличается. . .	FPS контроллер с анимированными Y-Bot и 3D-звуком miniaudio (Box3D, Recast, BehaviorTree.CPP, ozz-animation, ImGui, OpenGL и SDL3) 8Observer8 18.10.2026 Содержание блога \| English Version Полное мультиплатформенное руководство по стартовому проекту с FPS-контроллером игрока, анимированными роботами Y-Bot с 4-слойным блендингом, 3D-физикой Box3D,. . .
Локальный http сервер Argus19 17.10.2026 Локальный http сервер На работе, на двух локальных компьютерах круглосуточно работают программы опроса приборов с записью в книги Excel,которые раз в сутки записываются на сервер компании. Т. к. . . .	Копировать Windows на новый диск на UEFI damix 17.10.2026 https:/ / uriesk. wordpress. com/ 2016/ 11/ 01/ move-window-10-to-ssd-on-a-uefi-dualboot-system-with-basic-linux-tools/ TL DR Вставляем диск, а старый подключаем через переходник, грузимся с лайва. . .	ИИ не может найти нужный язык в списке Supersumestria 05.10.2026 Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .	Новая последняя моя музыка в SUNO zorxor 05.10.2026 Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .

@aassii 26 / 25 / 14 Регистрация: 12.10.2018 Сообщений: 240

	Определить, существует ли маршрут (вариант обхода графа), удовлетворяющий заданным критериям 27.02.2019, 19:31. Показов 4655. Ответов 25 Метки нет (Все метки) Задано прямоугольное поле n × m, в одной из ячеек в момент времени 1 появляется турист. Каждую секунду он переходит в одну из 4-х соседних ячеек, в которой он еще не был, а при переходе в новую клетку девайс туриста старательно отсылает вам номер секунды, на которой он оказался в клетке. Турист никогда надолго не задерживается, а после перехода мгновенно выбирает следующую точку, и за одну секунду оказывается в ней. После того, как турист обходил все поле, data - центр собрал для вас всю информацию в виде таблицы a размером n × m, где a_ij - время, когда турист здесь появился. Нужно определить, существует ли такой маршрут, что обходит всю таблицу, обходит все клетки по одному разу и для каждой ячейки делает это в момент времени a_ij. Входные данные: В первой строке входного файла содержится два целых числа n, m (1 ≤ n, m ≤ 1000) - размеры таблицы. В следующих n строках содержится по m целых чисел в каждой строке aij (1 ≤ a_ij ≤ 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

@aassii 26 / 25 / 14 Регистрация: 12.10.2018 Сообщений: 240
	03.03.2019, 16:28 [ТС]
	L0M, Вадим Тукаев, всем спасибо за помощь! Все ваши три программы прошли все тесты только после отключения синхронизации между потоками ввода вывода С и С++. 0

@L0M Мозгоправ 1745 / 1039 / 468 Регистрация: 01.10.2018 Сообщений: 2,138 Записей в блоге: 2
	03.03.2019, 17:47
	aassii, а по скорости выполнения доступна статистика? Из трёх вариантов какой самый быстрый? 0

@aassii 26 / 25 / 14 Регистрация: 12.10.2018 Сообщений: 240
	03.03.2019, 18:40 [ТС]
	Это результаты работы программ после отключения синхронизации между потоками ввода вывода С и С++. 0

@L0M Мозгоправ 1745 / 1039 / 468 Регистрация: 01.10.2018 Сообщений: 2,138 Записей в блоге: 2
	03.03.2019, 19:04
	Спасибо за результаты. Ну да, примерно как и ожидалось. 0