Тема: Визначити, чи існує маршрут, що задовольняє заданим критеріям
Можете допомогти за алгоритмом написати код програми?
Алгоритм:
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;
}