1

Тема: Визначити, чи існує маршрут, що задовольняє заданим критеріям

Можете допомогти за алгоритмом написати код програми?

Алгоритм:

Прихований текст

1. Зробити двовимірний динамічний масив і ввести в нього дані.
2. Знайти в масиві стартовий елемент, що містить 1 (це можна зробити ще при читанні даних).
3. Обчислити кількість елементів масиву (кількість рядків * кількість стовпців).
4. Зробити стартовий елемент поточним (координати: рядок, стовпець).
5. Заводимо лічильник маршруту і ініціалізуємо його 1.
6. У циклі:
- Перевіряємо сусідні чотири елементи (з урахуванням меж масиву) на значення на одиницю більше, ніж значення поточного елемента. Якщо таких елементів більше одного, значить вхідні дані некоректні - відразу NO і вихід з циклу. Якщо таких елементів немає, перевіряємо лічильник маршруту. Якщо його значення дорівнює кількості елементів масиву - ми в кінцевій точці - YES і вихід з циклу, інакше - NO і вихід з циклу.
- Є єдиний елемент, значення якого більше поточного на 1. Робимо його поточним.
- Збільшуємо лічильник маршруту.
7. Після виходу з циклу звільняємо пам'ять, виділену під двовимірний динамічний масив.

Умова:

Прихований текст

Задано прямокутне поле 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

Спроба написати код:

Прихований текст
#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;

//???

return 0;
}
Подякували: FakiNyan1

2

Re: Визначити, чи існує маршрут, що задовольняє заданим критеріям

aassii написав:

Можете допомогти за алгоритмом написати код програми?

Та можемо, але нащо це нам? І головне - нащо це вам? У вас непогано почалося, чому б не продовжити?
Для початку - розкладіть алгоритм на коментарі:

#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) ); //1. Зробити двовимірний динамічний масив...
    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;} //2. Знайти в масиві стартовий елемент, що містить 1 (це можна зробити ще при читанні даних).
        }
    int k_nm=n*m; //3. Обчислити кількість елементів масиву (кількість рядків * кількість стовпців).
    int start_g=g[start_i][start_j]; //4. Зробити стартовий елемент поточним (координати: рядок, стовпець).
    int counter=1; //5. Заводимо лічильник маршруту і ініціалізуємо його 1.

    /*6. У циклі:
    - Перевіряємо сусідні чотири елементи (з урахуванням меж масиву) на значення на одиницю більше, ніж значення поточного елемента. Якщо таких елементів більше одного, значить вхідні дані некоректні - відразу NO і вихід з циклу. Якщо таких елементів немає, перевіряємо лічильник маршруту. Якщо його значення дорівнює кількості елементів масиву - ми в кінцевій точці - YES і вихід з циклу, інакше - NO і вихід з циклу.
    - Є єдиний елемент, значення якого більше поточного на 1. Робимо його поточним.
    - Збільшуємо лічильник маршруту.*/
    //тут буде викликано деструктори vector -7. Після виходу з циклу звільняємо пам'ять, виділену під двовимірний динамічний масив.
return 0;
}

Як бачите, лишилося написати самий цикл, все решта вже є. Єдине що, вам не потрібні окремі стартовий і поточний елементи - бо спочатку ви виставляєте стартовий на 1, а потім рухаєте поточний починаючи з 1, а стартовий вам уже не потрібен.

3

Re: Визначити, чи існує маршрут, що задовольняє заданим критеріям

Так, ви праві, вам це не потрібно. А нам задали таке завдання по темі графи. Хоча цей алгоритм і не на графи, я гадаю, що він може не пройти всі тести по часу (Time-limit <0.250).

4 Востаннє редагувалося koala (03.03.2019 11:47:15)

Re: Визначити, чи існує маршрут, що задовольняє заданим критеріям

Просто я не розумію, у чому ваша проблема. Ви навчаєтеся, вам дали завдання - чому ви не можете це зробити? Алгоритм розжований майже до рівня псевдокоду. Ви або самі платите за те, щоб вас цьому навчили; або за вас платимо ми - платники податків. Вам воно не треба вміти? То переходьте на іншу спеціальність, не витрачайте дарма гроші.
Стосовно складності - цей алгоритм, очевидно, має складність О(m*n). Оскільки 1≤n,m≤1000, то циклів знадобиться мільйон. Якщо прийняти, що одна ітерація циклу вимагатиме 100 тактів процесора (це складно оцінити, тим більш без коду), то всього знадобиться 100 мільйонів тактів - на сучасному 3ГГц процесорі це 1/30 секунди. Але в цілому час треба оцінювати для вже написаного коду - дочасна оптимізація може сильно нашкодити. І принципово кращого не буде - вам же треба перевірити кожну комірку з мільйону, тобто в будь-якому разі буде O(m*n). Можна хіба що в деяких випадках швидше відкинути можливість побудови такого шляху - але повний шлях все одно треба перевіряти за O(m*n) кроків.