Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- vector <bool> Visited(1000);
- vector <int> Path;
- bool s[64][64];
- int free_N=0;
- int n, m;
- bool hamilton(int curr, int end)
- {
- Path.push_back(curr); //добавить текущую вершину графа в список
- if (Path.size() == free_N && curr == end)
- {
- //если размер пути равен количеству нулей и текущая (последняя)
- //вершина является той, путь к которой мы ищем, то конец. Решение построено
- return true;
- }
- //в эту часть заходит, если решение ещё не найдено
- Visited[curr] = true; //помечаем текущую вершину посещенной
- for (int next = 0; next < n*m; ++next)
- //далее ищем следующую вершину
- if (s[curr][next] == 1 && !Visited[next])
- //если вершина смежна с текущей и она ещё не посещена,
- //то вызываем этот же алгоритм рекурсивно для поиска следующей вершины
- if (hamilton(next,end))
- //если функция вернула true, то путь уже найден. И вернется
- //true для всех остальных веток рекурсии
- return true;
- Visited[curr] = false;
- //иначе, выбранная вершина была ошибочная, удаляем её из пути
- //и помечаем не посещенной
- Path.pop_back();
- return false;
- }
- int main()
- {
- cin >> n >> m;
- int x1, x2, y1, y2;
- cin >> x1 >> y1 >> x2 >> y2; //ввод начальной и конечной точки
- int begin = x1*m+y1, end = x2*m+y2;
- bool in[8][8];
- for (int i = 0; i < n; i++)
- for (int j = 0; j < m; j++) cin >> in[i][j];
- for (int i = 0; i < m*n; i++)
- for (int j = 0; j < m*n; j++)
- {
- s[i][j] = 0;
- }
- for (int i = 0; i < n; i++) //построение матрицы смежности
- {
- for (int j = 0; j < m; j++)
- {
- if (in[i][j]) continue;
- free_N++;
- if (i + 1 < n && in[i + 1][j] == 0)
- {
- s[(i + 1)*m + j][i*m + j] = 1;
- s[i*m + j][(i + 1)*m + j] = 1;
- }
- if (j + 1 < m && in[i][j + 1] == 0)
- {
- s[i*m + j + 1][i*m + j] = 1;
- s[i*m + j][i*m + j + 1] = 1;
- }
- }
- }
- hamilton(begin, end); //сам алгоритм
- cout << "Path: n";
- for (int i = 0; i < Path.size(); i++) cout << "[" << Path[i] / m << "][" << Path[i] % m << "] " << endl;
- cout << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement