Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <map>
- #include <deque>
- #include <windows.h>
- using namespace std;
- char matrix[100][100];
- map<pair<int, int>, pair<int, int>> pr;
- deque <pair<int,int>> rest;
- bool used[100][100];
- int dx[4] = { 1, -1, 0, 0 };
- int dy[4] = { 0, 0, -1, 1 };
- int n, m;
- void bfs(int x, int y)
- {
- used[x][y] = 1;
- rest.push_back(make_pair(x, y));
- while (rest.size())
- {
- pair<int, int>t = rest.front();
- rest.pop_front();
- x = t.first;
- y = t.second;
- for (int i = 0; i < 4; i++)
- {
- 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]])
- {
- used[x + dx[i]][y + dy[i]] = 1;
- rest.push_back(make_pair(x + dx[i], y + dy[i]));
- pr[make_pair(x + dx[i], y + dy[i])] = make_pair(x, y);
- }
- }
- }
- }
- int main()
- {
- cin >> n >> m;
- int x1, y1, x2, y2;
- for (int i = 0; i < n; i++)
- {
- for (int j = 0; j < m; j++)
- {
- cin >> matrix[i][j];
- if (matrix[i][j] == 'X')
- {
- x1 = i, y1 = j;
- }
- if (matrix[i][j] == 'O')
- {
- x2 = i, y2 = j;
- }
- }
- }
- bfs(x1, y1);
- if (!used[x2][y2])
- {
- cout << "There is no way";
- return 0;
- }
- pair<int, int> kr = pr[make_pair(x2, y2)];
- pair<int, int> er = { x1,y1 };
- while (kr!=er)
- {
- matrix[kr.first][kr.second] = '+';
- kr = pr[kr];
- for (int i = 0; i < n; i++)
- {
- cout << endl;
- for (int j = 0; j < n; j++)
- {
- cout << matrix[i][j];
- }
- }
- Sleep(1000);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement