Advertisement
Guest User

Untitled

a guest
Aug 23rd, 2017
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.84 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. vector <bool> Visited(1000);
  5. vector <int> Path;
  6. bool s[64][64];
  7. int free_N=0;
  8. int n, m;
  9. bool hamilton(int curr, int end)
  10. {
  11. Path.push_back(curr); //добавить текущую вершину графа в список
  12. if (Path.size() == free_N && curr == end)
  13. {
  14. //если размер пути равен количеству нулей и текущая (последняя)
  15. //вершина является той, путь к которой мы ищем, то конец. Решение построено
  16. return true;
  17. }
  18. //в эту часть заходит, если решение ещё не найдено
  19. Visited[curr] = true; //помечаем текущую вершину посещенной
  20. for (int next = 0; next < n*m; ++next)
  21. //далее ищем следующую вершину
  22. if (s[curr][next] == 1 && !Visited[next])
  23. //если вершина смежна с текущей и она ещё не посещена,
  24. //то вызываем этот же алгоритм рекурсивно для поиска следующей вершины
  25. if (hamilton(next,end))
  26. //если функция вернула true, то путь уже найден. И вернется
  27. //true для всех остальных веток рекурсии
  28. return true;
  29. Visited[curr] = false;
  30. //иначе, выбранная вершина была ошибочная, удаляем её из пути
  31. //и помечаем не посещенной
  32. Path.pop_back();
  33. return false;
  34. }
  35.  
  36. int main()
  37. {
  38. cin >> n >> m;
  39. int x1, x2, y1, y2;
  40. cin >> x1 >> y1 >> x2 >> y2; //ввод начальной и конечной точки
  41. int begin = x1*m+y1, end = x2*m+y2;
  42. bool in[8][8];
  43. for (int i = 0; i < n; i++)
  44. for (int j = 0; j < m; j++) cin >> in[i][j];
  45. for (int i = 0; i < m*n; i++)
  46. for (int j = 0; j < m*n; j++)
  47. {
  48. s[i][j] = 0;
  49. }
  50. for (int i = 0; i < n; i++) //построение матрицы смежности
  51. {
  52. for (int j = 0; j < m; j++)
  53. {
  54. if (in[i][j]) continue;
  55. free_N++;
  56. if (i + 1 < n && in[i + 1][j] == 0)
  57. {
  58. s[(i + 1)*m + j][i*m + j] = 1;
  59. s[i*m + j][(i + 1)*m + j] = 1;
  60. }
  61. if (j + 1 < m && in[i][j + 1] == 0)
  62. {
  63. s[i*m + j + 1][i*m + j] = 1;
  64. s[i*m + j][i*m + j + 1] = 1;
  65. }
  66. }
  67. }
  68. hamilton(begin, end); //сам алгоритм
  69. cout << "Path: n";
  70. for (int i = 0; i < Path.size(); i++) cout << "[" << Path[i] / m << "][" << Path[i] % m << "] " << endl;
  71. cout << endl;
  72. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement