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

@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

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

Новые блоги и статьи Все статьи Все блоги /
SUNO Ai - Река Без Дна zorxor 31.07.2026 Автор стихотворения - астрофизик Марина Катыс Ссылка на сгенерированную музыкальную композицию: https:/ / suno. com/ song/ 6f6e5464-b290-4650-be6c-44c85f8d8013 Я говорю, что Время- как вода течет. . .	Из невошедшего на форум (диалог с ИИ-гугла) zorxor 29.07.2026 А вот, что интересно, сказал мне ИИ-гугла: Этот текст — эмоциональный пост пользователя под ником zorxor на интернет-форуме (вероятно, посвященном мистике, непознанному или альтернативной науке). . . .	Был праздник вчера, а я и не знал. kumehtar 28.07.2026 27. 07. 2026г. Intel Core 2 Duo исполнилось 20 лет Новости компьютерного мира и их обсуждение (4) Салют, шампанское, овации! :drink:	Нейтральные знания, чистый код - бла-бла-бла-бла, на самом деле кликбейт и самореклама, плагиат, и вот почему Hrethgir 27.07.2026 То-есть отклонение такой публикации говорит само за себя, и пусть только возьмут на вооружение после отклонения публикации - это будет чистейшим актом плагиата. Отклонял Хабр. Дословно, отклонённая. . .
тв 16 бой ии anaschu 27.07.2026 Великий Перелом ИИ: Как уравнения ОДУ Radau дожали цензурные фильтры Алисы Фиксируем в мемофонде Теории Всего беспрецедентный факт в истории ИИ-зондирования. В затяжном многораундовом. . .	мв 15. непроверенное, возможно, глюк anaschu 27.07.2026 НАУЧНО-АНАЛИТИЧЕСКИЙ ОТЧЕТ. РАЗДЕЛ 1. 1: «НАУКА» (РАСШИРЕННАЯ СТЕХИОМЕТРИЧЕСКАЯ И ГЕНЕТИЧЕСКАЯ ВЕРСИЯ)Тема: Теоретическое обоснование инвариантности 19-мерного тензорного ядра непрерывных ОДУ и. . .	Очистка реквизитов и табличных частей документа при копировании (вариант 2) Maks 26.07.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРаботу", разработанного в КА2. Задача: Заменить алгоритм запрета копирования документов для сотрудников с ролью "Стажер",. . .	Доктрина интенционального знания - Доктрина для портала "Срез". Hrethgir 25.07.2026 Может найдётся кто захочет оценить доктрину. . . Написания правил участия для меня роскошь, требующая лимита времени, поэтому все сообщения не прошедшие модерацию будут видны только участникам портала,. . .

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

	Определить, существует ли маршрут (вариант обхода графа), удовлетворяющий заданным критериям 27.02.2019, 19:31. Показов 4541. Ответов 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