Advertisement
Guest User

Untitled

a guest
Mar 29th, 2017
52
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.78 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <algorithm>
  5. #include <queue>
  6. #include <set>
  7. #include <clocale>
  8.  
  9. using namespace std;
  10.  
  11. int main()
  12. {
  13. #ifdef _DEBUG
  14. freopen("input.txt","r",stdin);
  15. freopen("output.txt","w",stdout);
  16. #endif
  17. string start, fin, coord;
  18. getline(cin, start);
  19. getline(cin, fin);
  20.  
  21. pair <int, int> strt, fn;
  22. queue<pair<int, int> > q;
  23. vector<vector<int>>p1(8, vector<int> (8, -1));
  24. //vector<vector<int>>p1(8, vector<int> (8, -1));
  25. int dy[8] = {1, 2, -1, -2, -2, -1, 1, 2};
  26. int dx[8] = {2, 1, 2, 1, -1, -2, -2, -1};
  27.  
  28. // initialize #-s and strt and fn
  29. if (getline(cin, coord))
  30. for (int i = 0; i < coord.size(); i += 2)
  31. p1[coord[i] - 'A'][coord[i + 1] - '1'] = 8;
  32. strt = make_pair(start[0] - 'A', start[1] - '1');
  33. fn = make_pair(fin[0] - 'A', fin[1] - '1');
  34. p1[strt.first][strt.second] = 8;
  35. q.push(make_pair(strt.first, strt.second));
  36. // BFS
  37. while(!q.empty() && q.front() != fn)
  38. {
  39. int x = q.front().first, y = q.front().second;
  40. q.pop();
  41. for (int k = 0; k < 8; ++k)
  42. {
  43. int nx = x + dx[k];
  44. int ny = y + dy[k];
  45.  
  46. if (0 <= nx && nx < 8 && 0 <= ny && ny < 8 && p1[nx][ny] != 8 && p1[nx][ny] == -1)
  47. {
  48. p1[nx][ny] = k;
  49. q.push(make_pair(nx, ny));
  50. }
  51. }
  52. }
  53. // end BFS
  54. if (p1[fn.first][fn.second] == -1)
  55. {
  56. cout << 0;
  57. return 0;
  58. }
  59.  
  60. vector <int> path;
  61. int r = p1[fn.first][fn.second];
  62. while(r != 8)
  63. {
  64. path.push_back(r);
  65. fn.first -= dx[r], fn.second -= dy[r];
  66. r = p1[fn.first][fn.second];
  67. }
  68. reverse(path.begin(), path.end());
  69. for (int l = 0; l < path.size(); ++l)
  70. {
  71. cout << char('A' + strt.first) << strt.second + 1;
  72. strt = make_pair(strt.first + dx[l], strt.second + dy[l]);
  73. }
  74. cout << char('A' + strt.first) << strt.second + 1;
  75.  
  76. return 0;
  77. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement