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

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

27.02.2019, 19:31. Показов 3496. Ответов 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
Мозгоправ
1737 / 1031 / 468
Регистрация: 01.10.2018
Сообщений: 2,138
Записей в блоге: 2
27.02.2019, 19:45 2
А какие сложности? Вроде всё просто.
0
23 / 23 / 13
Регистрация: 12.10.2018
Сообщений: 240
27.02.2019, 20:49  [ТС] 3
Только начали изучать графы - пока все сложно!
0
Мозгоправ
1737 / 1031 / 468
Регистрация: 01.10.2018
Сообщений: 2,138
Записей в блоге: 2
28.02.2019, 01:12 4
Ну наверное можно под это подложить теорию графов...
Но, как я вижу, решается всё просто, безо всякой теории.
  1. Сделать двумерный динамический массив и всосать в него данные.
  2. Найти в массиве стартовый элемент, содержащий 1 (это можно сделать ещё при чтении данных).
  3. Вычислить количество элементов массива (кол-во строк * кол-во столбцов).
  4. Сделать стартовый элемент текущим (координаты: строка, столбец).
  5. Заводим счётчик маршрута и инициализируем его 1.
  6. В цикле:
    1. Проверяем соседние четыре элемента (с учётом границ массива) на значение на единицу большее, чем значение текущего элемента. Если таких элементов более одного, значит входные данные некорректны - сразу NO и выход из цикла. Если таких элементов нет, проверяем счётчик маршрута. Если его значение равно количеству элементов массива - мы в конечной точке - YES и выход из цикла, иначе - NO и выход из цикла.
    2. Есть единственный элемент, значение которого больше текущего на 1. Делаем его текущим.
    3. Инкрементируем счётчик маршрута.
  7. После выхода из цикла освобождаем память, выделенную под двумерный динамический массив.
Как-то так.
1
23 / 23 / 13
Регистрация: 12.10.2018
Сообщений: 240
01.03.2019, 22:56  [ТС] 5
L0M, спасибо за алгоритм. Подскажите пожалуйста, где наделал ошибки?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <vector>
using namespace std;
int main()
{
    int n,m,start_i,start_j;
    cin>>n>>m;
    vector<vector<int> > g(n, vector<int> (m) );
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
        {
            cin>>g[i][j]; if (g[i][j]==1) {start_i=i;start_j=j;}
        }
    int k_nm=n*m;
    int start_g=g[start_i][start_j];
    int counter=1;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            int element4=0;
            if (i>0)   if (start_g+1==g[i-1][j]) {element4++;}
            if (i<n-1) if (start_g+1==g[i+1][j]) {element4++;}
            if (j>0)   if (start_g+1==g[i][j-1]) {element4++;}
            if (j<m-1) if (start_g+1==g[i][j+1]) {element4++;}
            if (element4>1) {cout<<"NO"<<endl; break;}
            if (element4==0)
                if (counter==k_nm) {cout<<"YES"<<endl; break;}
                    else {cout<<"NO"<<endl; break;}
            start_g=g[i][j];
            counter++;
        }
    }
    return 0;
}
0
Мозгоправ
1737 / 1031 / 468
Регистрация: 01.10.2018
Сообщений: 2,138
Записей в блоге: 2
02.03.2019, 01:17 6
Цитата Сообщение от aassii Посмотреть сообщение
Подскажите пожалуйста, где наделал ошибки?
С 17-й строки и далее.

У меня сложилось впечатление, что вы очень смутно понимаете, что вы кодите.

Вот например, вы пишите два вложенных цикла (17 и 19 строка). Зачем? Можете объяснить?
Причём в алгоритме я дал подсказку (не специально), употребив в п.6 слово "цикл" в единственном числе.

А дальше уже цепляется одно за другое.
0
23 / 23 / 13
Регистрация: 12.10.2018
Сообщений: 240
02.03.2019, 02:14  [ТС] 7
Вы правы, потому и прошу помощи.
Думал надо проверять соседние четыре элемента в исходном двумерном масиве вокруг (i,j) элемента, чтобы найти соседний на единичку больше.
0
Мозгоправ
1737 / 1031 / 468
Регистрация: 01.10.2018
Сообщений: 2,138
Записей в блоге: 2
02.03.2019, 14:52 8
Цитата Сообщение от aassii Посмотреть сообщение
Думал надо проверять соседние четыре элемента в исходном двумерном масиве вокруг (i,j) элемента, чтобы найти соседний на единичку больше.
Да, надо. Только для этого не нужен двойной цикл по всему массиву. Хватит проверки конкретных четырёх элементов с учётом границ массива.

А цикл из п.6 реализует проход туриста по маршруту. И, чисто логически, это скорее всего либо do/while, либо бесконечный цикл с выходом(-ами) по break.

Возможно имеет смысл сделать структуру, содержащую пару координат элемента в массиве.
Возможно имеет смысл сделать функцию, которая вычисляет следующее положение туриста, если оно возможно и корректно.

Я могу написать эту программу за вас. Но это уже не будет помощью.
0
23 / 23 / 13
Регистрация: 12.10.2018
Сообщений: 240
02.03.2019, 17:37  [ТС] 9
Цитата Сообщение от L0M Посмотреть сообщение
Я могу написать эту программу за вас. Но это уже не будет помощью.
Согласен.
Но если вам не сложно то напишите пожалуйста. И желательно коментарий к ключевым моментам (например, вычисление следующего положения туриста).
Желательно без функции, хотя с функцией будет нагляднее.
0
Мозгоправ
1737 / 1031 / 468
Регистрация: 01.10.2018
Сообщений: 2,138
Записей в блоге: 2
02.03.2019, 23:10 10
Цитата Сообщение от aassii Посмотреть сообщение
Сообщение от L0M
Я могу написать эту программу за вас. Но это уже не будет помощью.
Согласен.
Но если вам не сложно то напишите пожалуйста
Вы не ощущаете некую абсурдность ситуации? И здесь тоже:
Цитата Сообщение от aassii Посмотреть сообщение
Желательно без функции, хотя с функцией будет нагляднее.
А самому пошевелить мозгами совсем никак?
0
23 / 23 / 13
Регистрация: 12.10.2018
Сообщений: 240
02.03.2019, 23:36  [ТС] 11
Во первых мы только начали изучать тему графы, а во вторых - нехватает у меня мозгов))
0
ReDoX
03.03.2019, 00:07
  #12

Не по теме:

Цитата Сообщение от aassii Посмотреть сообщение
Во первых мы только начали изучать тему графы
Причем тут графы? В решении выше ими и не пахнет

0
Мозгоправ
1737 / 1031 / 468
Регистрация: 01.10.2018
Сообщений: 2,138
Записей в блоге: 2
03.03.2019, 01:59 13
Лучший ответ Сообщение было отмечено aassii как решение

Решение

Цитата Сообщение от aassii Посмотреть сообщение
нехватает у меня мозгов))
Ну, значит не судьба

Вариант 1.
По вышеприведённому алгоритму.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <iostream>
#include <iomanip>
 
using namespace std;
 
struct Coord {
    int m_col, m_row;
    Coord() : m_col(0), m_row(0) {}
    Coord(int x, int y) : m_col(x), m_row(y) {}
 
    void set(int x, int y) {
        m_col = x; m_row = y;
    }
 
    bool isGood(const Coord &border) {
        return m_col >= 0 && m_row >= 0 && m_col < border.m_col && m_row < border.m_row;
    }
 
    Coord & operator+=(const Coord &rh) {
        m_col += rh.m_col;
        m_row += rh.m_row;
        return *this;
    }
};
 
bool find_next_location(int **locations, const Coord &border, Coord &loc) {
    static const int dirs = 4;          // количество направлений
    static const Coord dif[dirs] = {    // массив изменений координат по направлениям
        {  1,  0 },                     // движение вправо
        {  0,  1 },                     // движение вниз
        { -1,  0 },                     // движение влево
        {  0, -1 }                      // движение вверх
    };
    const int next_time = locations[loc.m_row][loc.m_col] + 1;  // следующее время
    Coord temp, next;
    int cnt = 0;                        // счётчик подходящих соседних клеток
 
    // проверка по всем направлениям
    for (int i = 0; i < dirs; ++i) {
        temp = loc;                     // текущее положение
        temp += dif[i];                 // сдвигаемся на соседнюю клетку
        if (temp.isGood(border)) {      // координаты не выходят за пределы таблицы?
            if (locations[temp.m_row][temp.m_col] == next_time) {
                                        // время совпадает с ожидаемым
                ++cnt;
                next = temp;            // запоминаем предполагаемое следующее положение туриста
            }
        }
    }
 
    if (cnt == 1) {                     // для следующего положения туриста есть только один вариант
        loc = next;                     // возвращаем найденное положение
        return true;                    // сигнализируем об успехе
    }
    return false;
}
 
int main() {
 
    int n, m;
    cin >> n >> m;
 
    // создать двухмерный динамический массив
    int **locations = new int *[n];
    for (int i = 0; i < n; ++i)
        locations[i] = new int[m];
 
    const Coord border(m, n);           // границы таблицы
    bool finish = true;                 // флаг, что путешествие закончено
    Coord loc;                          // текущее положение туриста
 
    // заполнить массив данными и вычислить координаты начала маршрута
    int time;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) {
            cin >> time;
            locations[i][j] = time;
            if (time == 1) {
                loc.set(j, i);          // нашли начало маршрута
                finish = false;         // можно начинать путешествие
            }
        }
 
    int route_counter = 1;              // счётчик маршрута
    const int route_len = n * m;        // длина маршрута
 
    while (!finish) {
        finish = !find_next_location(locations, border, loc);
        if (!finish)
            ++route_counter;
    }
 
    cout << (route_counter == route_len ? "YES" : "NO") << endl;
 
    // удалить двухмерный динамический массив
    for (int i = 0; i < n; ++i)
        delete[] locations[i];
    delete[] locations;
 
    return 0;
}
Вариант 2.
For fun
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
 
using namespace std;
 
struct Location {
    int m_time;
    int m_col, m_row;
    Location(int x, int y, int time) : m_time(time), m_col(x), m_row(y) {}
};
 
typedef vector<Location> Locations;
 
int main() {
 
    Locations site;
    int n, m;
    int time;
 
    cin >> n >> m;
    for (int y = 0; y < n; ++y) {
        for (int x = 0; x < m; ++x) {
            cin >> time;
            site.emplace_back(x, y, time);
        }
    }
 
    sort(site.begin(), site.end(), [](const Location &lh, const Location &rh) { return lh.m_time < rh.m_time; });
 
    bool result = true;
    Location &prev = site[0];
    for (size_t i = 1; i < site.size(); ++i) {
        Location &loc = site[i];
        if (loc.m_time != prev.m_time + 1) {
            result = false;
            break;
        }
        if (!((1 == abs(prev.m_col - loc.m_col) && prev.m_row == loc.m_row)
            || (1 == abs(prev.m_row - loc.m_row) && prev.m_col == loc.m_col))) {
            result = false;
            break;
        }
        prev = loc;
    }
 
    cout << (result ? "YES" : "NO") << endl;
 
    return 0;
}
1
23 / 23 / 13
Регистрация: 12.10.2018
Сообщений: 240
03.03.2019, 02:48  [ТС] 14
L0M, Огромное спасибо! Очень помогли!

ReDoX,
Цитата Сообщение от ReDoX Посмотреть сообщение
Не по теме:
Сообщение от aassii
Во первых мы только начали изучать тему графы
Причем тут графы? В решении выше ими и не пахнет
Вот теперь понятно, почему эту задачу нужно решать на графы. Не проходит один тест - Time-limit exceeded >0.250.
0
303 / 284 / 116
Регистрация: 23.01.2018
Сообщений: 933
03.03.2019, 08:30 15
Лучший ответ Сообщение было отмечено aassii как решение

Решение

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <algorithm>
#include <iostream>
#include <vector>
 
using namespace std;
 
int main(void)
{
    int n, m;
    cin >> n >> m;
    vector<pair<int,int>> map(n * m);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            int t;
            cin >> t;
            map[t - 1] = make_pair(i, j);
        }
    }
    cout << (mismatch(map.cbegin() + 1, map.cend(), map.cbegin(),
        [](auto a, auto b) {
            int dx = abs(a.first - b.first);
            int dy = abs(a.second - b.second);
            return dx == 0 && dy == 1 || dx == 1 && dy == 0;
        }).first == map.cend() ? "YES" : "NO") << endl;
    return 0;
}
1
23 / 23 / 13
Регистрация: 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
303 / 284 / 116
Регистрация: 23.01.2018
Сообщений: 933
03.03.2019, 14:53 17
Лучший ответ Сообщение было отмечено aassii как решение

Решение

Ну так всего делов избавиться от auto.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <algorithm>
#include <iostream>
#include <vector>
 
using namespace std;
 
int main(void)
{
    int n, m;
    cin >> n >> m;
    vector<pair<int,int>> map(n * m);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            int t;
            cin >> t;
            map[t - 1] = make_pair(i, j);
        }
    }
    cout << (mismatch(map.cbegin() + 1, map.cend(), map.cbegin(),
        [](pair<int,int> a, pair<int,int> b) {
            int dx = abs(a.first - b.first);
            int dy = abs(a.second - b.second);
            return dx == 0 && dy == 1 || dx == 1 && dy == 0;
        }).first == map.cend() ? "YES" : "NO") << endl;
    return 0;
}
1
Мозгоправ
1737 / 1031 / 468
Регистрация: 01.10.2018
Сообщений: 2,138
Записей в блоге: 2
03.03.2019, 15:23 18
Вадим Тукаев, ваше решение валится на входных данных:
Код
3 4
1 2 9 10
4 3 8 11
5 6 7 1200
Цитата Сообщение от aassii Посмотреть сообщение
не могу сдать ваш вариант программы потому, что в проверяющей системе используется компилятор С++11.
Похоже, что компилятору не нравится auto в переметрах лямбды. Попробуйте их заменить на pair<int,int>.

Добавлено через 13 минут
Цитата Сообщение от aassii Посмотреть сообщение
Не проходит один тест - Time-limit exceeded >0.250
Оба моих варианта не проходят по времени?
0
303 / 284 / 116
Регистрация: 23.01.2018
Сообщений: 933
03.03.2019, 15:45 19
Цитата Сообщение от L0M Посмотреть сообщение
Вадим Тукаев, ваше решение валится на входных данных:
Потому что эти входные данные не соответствуют условию задачи. Если я правильно понял задачу, то числа последовательные, от 1 до n * m. Но можно и для Вашего условия переделать. Суть алгоритма не изменится.
0
23 / 23 / 13
Регистрация: 12.10.2018
Сообщений: 240
03.03.2019, 16:04  [ТС] 20
L0M,
Цитата Сообщение от L0M Посмотреть сообщение
Оба моих варианта не проходят по времени?
Оба ваших варианта не проходят по времени один и тот же большой тест (Input: file is too large, original size 5653666)
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
03.03.2019, 16:04
Помогаю со студенческими работами здесь

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

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

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

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


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

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

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