Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <queue>
- #include <vector>
- using namespace std;
- const int inf = 1e9;
- struct Points{
- int nowX, nowY, value;
- };
- bool checkBorder(int &x, int &y, int &n, int &m){
- return (x >= 0 && x < n && y >= 0 && y < m);
- }
- int main(){
- int n, m;
- freopen("maze.in", "r", stdin);
- freopen("maze.out", "w", stdout);
- cin >> n >> m;
- int xStart, yStart, xFinish, yFinish;
- cin >> xStart >> yStart;
- cin >> xFinish >> yFinish;
- xStart--, yStart--;
- xFinish--, yFinish--;
- // if (xStart == xFinish && yStart == yFinish){
- // cout << 0 << endl;
- // return 0;
- // }
- int **minimalDistance = new int*[n];
- int **room = new int*[n];
- for (int i = 0; i < n; ++i){
- room[i] = new int [m];
- minimalDistance[i] = new int [m];
- for (int j = 0; j < m; ++j) {
- cin >> room[i][j];
- room[i][j] ^= 1;
- minimalDistance[i][j] = inf;
- }
- }
- queue <Points> q;
- q.push({xStart, yStart, 0});
- while (!q.empty()){
- Points Current = q.front();
- q.pop();
- if (!checkBorder(Current.nowX, Current.nowY, n, m)) continue;
- if (room[Current.nowX][Current.nowY]) continue;
- if (minimalDistance[Current.nowX][Current.nowY] <= Current.value) continue;
- minimalDistance[Current.nowX][Current.nowY] = Current.value;
- for (int delx = -1; delx <= 1; ++delx){
- for (int dely = -1; dely <= 1; ++dely) if ((delx == 0 && dely) || (delx && dely == 0)){
- q.push({Current.nowX + delx, Current.nowY + dely, Current.value + 1});
- }
- }
- }
- if (minimalDistance[xFinish][yFinish] == inf){
- cout << -1 << endl;
- return 0;
- }
- cout << minimalDistance[xFinish][yFinish] << endl;
- vector <pair <int, int> > ans;
- while (!(xFinish == xStart && yFinish == yStart)){
- ans.push_back({xFinish, yFinish});
- pair <int, int> to;
- int mn = inf;
- for (int delx = -1; delx <= 1; ++delx){
- for (int dely = -1; dely <= 1; ++dely) if ((delx == 0 && dely) || (delx && dely == 0)){
- xFinish += delx;
- yFinish += dely;
- if (checkBorder(xFinish, yFinish, n, m)) {
- if (mn > minimalDistance[xFinish][yFinish]){
- mn = minimalDistance[xFinish][yFinish];
- to = {xFinish, yFinish};
- }
- }
- xFinish -= delx;
- yFinish -= dely;
- }
- }
- xFinish = to.first;
- yFinish = to.second;
- }
- ans.push_back({xStart, yStart});
- for (int i = ans.size() - 1; i >= 0; i--){
- cout << ans[i].first + 1 << " " << ans[i].second + 1 << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement