Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <queue>
- using namespace std;
- const int inf = 1e9;
- vector < pair < int, int > > shift = { {-1, 0}, {1, 0}, {0, 1}, {0, -1} };
- int main() {
- int n;
- cin >> n;
- vector < vector < char > > a(n, vector < char >(n));
- pair < int, int > start, finish;
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < n; j++) {
- cin >> a[i][j];
- if (a[i][j] == '@') {
- start = { i, j };
- }
- if (a[i][j] == 'X') {
- finish = { i, j };
- }
- }
- }
- vector < vector < bool > > used(n, vector < bool >(n, false));
- vector < vector < int > > dist(n, vector < int >(n, inf));
- vector < vector < pair < int, int > > > par(n, vector < pair < int, int > >(n, {-1, -1}));
- queue < pair < int, int > > Q;
- Q.push(start);
- used[start.first][start.second] = true;
- dist[start.first][start.second] = 0;
- while (Q.size() != 0) {
- pair < int, int > v = Q.front();
- Q.pop();
- int x = v.first;
- int y = v.second;
- for (int i = 0; i < shift.size(); i++) {
- int nx = v.first + shift[i].first;
- int ny = v.second + shift[i].second;
- if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
- if (used[nx][ny] == false && a[nx][ny] != 'O') {
- dist[nx][ny] = dist[x][y] + 1;
- used[nx][ny] = true;
- par[nx][ny] = { x, y };
- Q.push({ nx, ny });
- }
- }
- }
- }
- if (dist[finish.first][finish.second] == inf) {
- cout << "N";
- system("pause");
- return 0;
- }
- int tx = finish.first, ty = finish.second;
- while (par[tx][ty] != make_pair(-1, -1)) {
- a[tx][ty] = '+';
- int qx = par[tx][ty].first;
- int qy = par[tx][ty].second;
- tx = qx;
- ty = qy;
- }
- cout << "Y\n";
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < n; j++) {
- cout << a[i][j];
- }
- cout << "\n";
- }
- system("pause");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement