Advertisement
haufont

Untitled

Aug 29th, 2016
345
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.49 KB | None | 0 0
  1. #include <iostream>
  2. #include <map>
  3. #include <deque>
  4. #include <windows.h>
  5. using namespace std;
  6.  
  7. char matrix[100][100];
  8. map<pair<int, int>, pair<int, int>> pr;
  9. deque <pair<int,int>> rest;
  10. bool used[100][100];
  11.  
  12. int dx[4] = { 1, -1, 0, 0 };
  13. int dy[4] = { 0, 0, -1, 1 };
  14. int n, m;
  15. void bfs(int x, int y)
  16. {
  17. used[x][y] = 1;
  18. rest.push_back(make_pair(x, y));
  19. while (rest.size())
  20. {
  21. pair<int, int>t = rest.front();
  22. rest.pop_front();
  23. x = t.first;
  24. y = t.second;
  25. for (int i = 0; i < 4; i++)
  26. {
  27. if (-1 < x + dx[i] < n && -1 < y + dy[i] < m && (matrix[x + dx[i]][y + dy[i]] == '.' || matrix[x + dx[i]][y + dy[i]] == 'O') && !used[x + dx[i]][y + dy[i]])
  28. {
  29. used[x + dx[i]][y + dy[i]] = 1;
  30. rest.push_back(make_pair(x + dx[i], y + dy[i]));
  31. pr[make_pair(x + dx[i], y + dy[i])] = make_pair(x, y);
  32. }
  33. }
  34. }
  35. }
  36. int main()
  37. {
  38. cin >> n >> m;
  39. int x1, y1, x2, y2;
  40. for (int i = 0; i < n; i++)
  41. {
  42. for (int j = 0; j < m; j++)
  43. {
  44. cin >> matrix[i][j];
  45. if (matrix[i][j] == 'X')
  46. {
  47. x1 = i, y1 = j;
  48. }
  49. if (matrix[i][j] == 'O')
  50. {
  51. x2 = i, y2 = j;
  52. }
  53. }
  54. }
  55. bfs(x1, y1);
  56. if (!used[x2][y2])
  57. {
  58. cout << "There is no way";
  59. return 0;
  60. }
  61. pair<int, int> kr = pr[make_pair(x2, y2)];
  62. pair<int, int> er = { x1,y1 };
  63. while (kr!=er)
  64. {
  65. matrix[kr.first][kr.second] = '+';
  66. kr = pr[kr];
  67. for (int i = 0; i < n; i++)
  68. {
  69. cout << endl;
  70. for (int j = 0; j < n; j++)
  71. {
  72. cout << matrix[i][j];
  73. }
  74. }
  75. Sleep(1000);
  76. }
  77. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement