Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <string>
- #include <algorithm>
- #include <queue>
- #include <set>
- #include <clocale>
- using namespace std;
- int main()
- {
- #ifdef _DEBUG
- freopen("input.txt","r",stdin);
- freopen("output.txt","w",stdout);
- #endif
- string start, fin, coord;
- getline(cin, start);
- getline(cin, fin);
- pair <int, int> strt, fn;
- queue<pair<int, int> > q;
- vector<vector<int>>p1(8, vector<int> (8, -1));
- //vector<vector<int>>p1(8, vector<int> (8, -1));
- int dy[8] = {1, 2, -1, -2, -2, -1, 1, 2};
- int dx[8] = {2, 1, 2, 1, -1, -2, -2, -1};
- // initialize #-s and strt and fn
- if (getline(cin, coord))
- for (int i = 0; i < coord.size(); i += 2)
- p1[coord[i] - 'A'][coord[i + 1] - '1'] = 8;
- strt = make_pair(start[0] - 'A', start[1] - '1');
- fn = make_pair(fin[0] - 'A', fin[1] - '1');
- p1[strt.first][strt.second] = 8;
- q.push(make_pair(strt.first, strt.second));
- // BFS
- while(!q.empty() && q.front() != fn)
- {
- int x = q.front().first, y = q.front().second;
- q.pop();
- for (int k = 0; k < 8; ++k)
- {
- int nx = x + dx[k];
- int ny = y + dy[k];
- if (0 <= nx && nx < 8 && 0 <= ny && ny < 8 && p1[nx][ny] != 8 && p1[nx][ny] == -1)
- {
- p1[nx][ny] = k;
- q.push(make_pair(nx, ny));
- }
- }
- }
- // end BFS
- if (p1[fn.first][fn.second] == -1)
- {
- cout << 0;
- return 0;
- }
- vector <int> path;
- int r = p1[fn.first][fn.second];
- while(r != 8)
- {
- path.push_back(r);
- fn.first -= dx[r], fn.second -= dy[r];
- r = p1[fn.first][fn.second];
- }
- reverse(path.begin(), path.end());
- for (int l = 0; l < path.size(); ++l)
- {
- cout << char('A' + strt.first) << strt.second + 1;
- strt = make_pair(strt.first + dx[l], strt.second + dy[l]);
- }
- cout << char('A' + strt.first) << strt.second + 1;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement