25 / 24 / 14
Регистрация: 12.10.2018
Сообщений: 240
|
|
1 | |
Определить, существует ли маршрут (вариант обхода графа), удовлетворяющий заданным критериям27.02.2019, 19:31. Показов 3685. Ответов 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
|
27.02.2019, 19:31 | |
Ответы с готовыми решениями:
25
Найти маршрут, включающий максимальное количество городов и удовлетворяющий вышеназванными условиям Методом обхода в глубину определить число компонент связности и цикломатическое число графа Существует ли алгоритм удовлетворяющий моим требованиям Определить, существует ли треугольник по двум заданным углам |
25 / 24 / 14
Регистрация: 12.10.2018
Сообщений: 240
|
|
27.02.2019, 20:49 [ТС] | 3 |
Только начали изучать графы - пока все сложно!
0
|
Мозгоправ
|
|
28.02.2019, 01:12 | 4 |
Ну наверное можно под это подложить теорию графов...
Но, как я вижу, решается всё просто, безо всякой теории.
1
|
25 / 24 / 14
Регистрация: 12.10.2018
Сообщений: 240
|
||||||
01.03.2019, 22:56 [ТС] | 5 | |||||
L0M, спасибо за алгоритм. Подскажите пожалуйста, где наделал ошибки?
0
|
Мозгоправ
|
|
02.03.2019, 01:17 | 6 |
С 17-й строки и далее.
У меня сложилось впечатление, что вы очень смутно понимаете, что вы кодите. Вот например, вы пишите два вложенных цикла (17 и 19 строка). Зачем? Можете объяснить? Причём в алгоритме я дал подсказку (не специально), употребив в п.6 слово "цикл" в единственном числе. А дальше уже цепляется одно за другое.
0
|
25 / 24 / 14
Регистрация: 12.10.2018
Сообщений: 240
|
|
02.03.2019, 02:14 [ТС] | 7 |
Вы правы, потому и прошу помощи.
Думал надо проверять соседние четыре элемента в исходном двумерном масиве вокруг (i,j) элемента, чтобы найти соседний на единичку больше.
0
|
Мозгоправ
|
|
02.03.2019, 14:52 | 8 |
Да, надо. Только для этого не нужен двойной цикл по всему массиву. Хватит проверки конкретных четырёх элементов с учётом границ массива.
А цикл из п.6 реализует проход туриста по маршруту. И, чисто логически, это скорее всего либо do/while, либо бесконечный цикл с выходом(-ами) по break. Возможно имеет смысл сделать структуру, содержащую пару координат элемента в массиве. Возможно имеет смысл сделать функцию, которая вычисляет следующее положение туриста, если оно возможно и корректно. Я могу написать эту программу за вас. Но это уже не будет помощью.
0
|
25 / 24 / 14
Регистрация: 12.10.2018
Сообщений: 240
|
|
02.03.2019, 17:37 [ТС] | 9 |
Согласен.
Но если вам не сложно то напишите пожалуйста. И желательно коментарий к ключевым моментам (например, вычисление следующего положения туриста). Желательно без функции, хотя с функцией будет нагляднее.
0
|
25 / 24 / 14
Регистрация: 12.10.2018
Сообщений: 240
|
|
02.03.2019, 23:36 [ТС] | 11 |
Во первых мы только начали изучать тему графы, а во вторых - нехватает у меня мозгов))
0
|
ReDoX
|
03.03.2019, 00:07
#12
|
0
|
Мозгоправ
|
|||||||||||
03.03.2019, 01:59 | 13 | ||||||||||
Сообщение было отмечено aassii как решение
Решение
Ну, значит не судьба
Вариант 1. По вышеприведённому алгоритму.
For fun
1
|
25 / 24 / 14
Регистрация: 12.10.2018
Сообщений: 240
|
|
03.03.2019, 02:48 [ТС] | 14 |
L0M, Огромное спасибо! Очень помогли!
ReDoX, Вот теперь понятно, почему эту задачу нужно решать на графы. Не проходит один тест - Time-limit exceeded >0.250.
0
|
307 / 288 / 116
Регистрация: 23.01.2018
Сообщений: 933
|
||||||
03.03.2019, 08:30 | 15 | |||||
Сообщение было отмечено aassii как решение
Решение
1
|
25 / 24 / 14
Регистрация: 12.10.2018
Сообщений: 240
|
|
03.03.2019, 12:51 [ТС] | 16 |
Вадим Тукаев, Спасибо большое за помощь, но не могу сдать ваш вариант программы потому, что в проверяющей системе используется компилятор С++11.
Compilation error: Кликните здесь для просмотра всего текста
000069.cpp: In function 'int main()':
000069.cpp:20:17: error: parameter declared 'auto' [](auto a, auto b) ^ 000069.cpp:20:25: error: parameter declared 'auto' [](auto a, auto b) ^ 000069.cpp: In lambda function: 000069.cpp:22:26: error: 'a' was not declared in this scope int dx = abs(a.first - b.first); ^ 000069.cpp:22:36: error: 'b' was not declared in this scope int dx = abs(a.first - b.first); ^ 000069.cpp:24:28: warning: suggest parentheses around '&&' within '||' [-Wparentheses] return dx == 0 && dy == 1 || dx == 1 && dy == 0; ^ In file included from /usr/include/c++/4.8/algorithm:61:0, from 000069.cpp:1: /usr/include/c++/4.8/bits/stl_algobase.h: In instantiation of 'std:air<_T1, _T2> std::mismatch(_InputIterator1, _InputIterator1, _InputIterator2, _BinaryPredicate) [with _InputIterator1 = __gnu_cxx::__normal_iterator<const std:air<int, int>*, std::vector<std:air<int, int> > >; _InputIterator2 = __gnu_cxx::__normal_iterator<const std:air<int, int>*, std::vector<std:air<int, int> > >; _BinaryPredicate = main()::__lambda0]': 000069.cpp:25:10: required from here /usr/include/c++/4.8/bits/stl_algobase.h:1206:76: error: no match for call to '(main()::__lambda0) (const std:air<int, int>&, const std:air<int, int>&)' while (__first1 != __last1 && bool(__binary_pred(*__first1, *__first2))) ^ 000069.cpp:20:10: note: candidates are: [](auto a, auto b) ^ In file included from /usr/include/c++/4.8/algorithm:61:0, from 000069.cpp:1: /usr/include/c++/4.8/bits/stl_algobase.h:1206:76: note: bool (*)() <conversion> while (__first1 != __last1 && bool(__binary_pred(*__first1, *__first2))) ^ /usr/include/c++/4.8/bits/stl_algobase.h:1206:76: note: candidate expects 1 argument, 3 provided 000069.cpp:20:26: note: main()::__lambda0 [](auto a, auto b) ^ 000069.cpp:20:26: note: candidate expects 0 arguments, 2 provided
0
|
307 / 288 / 116
Регистрация: 23.01.2018
Сообщений: 933
|
||||||
03.03.2019, 14:53 | 17 | |||||
Сообщение было отмечено aassii как решение
Решение
Ну так всего делов избавиться от auto.
1
|
Мозгоправ
|
|
03.03.2019, 15:23 | 18 |
Вадим Тукаев, ваше решение валится на входных данных:
Код
3 4 1 2 9 10 4 3 8 11 5 6 7 1200 auto в переметрах лямбды. Попробуйте их заменить на pair<int,int> .Добавлено через 13 минут Оба моих варианта не проходят по времени?
0
|
307 / 288 / 116
Регистрация: 23.01.2018
Сообщений: 933
|
|
03.03.2019, 15:45 | 19 |
Потому что эти входные данные не соответствуют условию задачи. Если я правильно понял задачу, то числа последовательные, от 1 до n * m. Но можно и для Вашего условия переделать. Суть алгоритма не изменится.
0
|
25 / 24 / 14
Регистрация: 12.10.2018
Сообщений: 240
|
|
03.03.2019, 16:04 [ТС] | 20 |
L0M,
Оба ваших варианта не проходят по времени один и тот же большой тест (Input: file is too large, original size 5653666)
0
|
03.03.2019, 16:04 | |
03.03.2019, 16:04 | |
Помогаю со студенческими работами здесь
20
Определить существует ли треугольник по заданным трем сторонам По заданным трём сторонам определить, существует ли треугольник, и, если да, то какой Определить все варианты остовных подграфов полного графа с заданным количеством ребер В заданном графе необходимо определить, существует ли цикл, проходящий по каждому ребру графа ровно 1 раз Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |