Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <fstream>
- #include <queue>
- using namespace std;
- void f(queue<pair<int, int>>& s, vector<vector<pair<int, int>>>& j, vector<vector<int>>& p, pair<int, int>& a, pair<int, int>& b, int o, int d)
- {
- if (b.first == o && b.second == d)
- {
- }
- else if (p[b.first][b.second] == 0)
- {
- s.push(b);
- p[b.first][b.second] = p[a.first][a.second] + 1;
- j[b.first][b.second] = a;
- }
- }
- void func(queue<pair<int, int>>& s, vector<vector<pair<int, int>>>& j, vector<vector<int>>& p, pair<int, int>& a, int o, int d)
- {
- pair<int, int> b;
- b.first = a.first + 1;
- b.second = a.second;
- if (b.first < p.size())
- f(s, j, p, a, b, o, d);
- b.first = a.first - 1;
- b.second = a.second;
- if (b.first >= 0)
- f(s, j, p, a, b, o, d);
- b.first = a.first;
- b.second = a.second + 1;
- if (b.second < p[b.first].size())
- f(s, j, p, a, b, o, d);
- b.first = a.first;
- b.second = a.second - 1;
- if (b.second >= 0)
- f(s, j, p, a, b, o, d);
- }
- int main()
- {
- ifstream fin("maze.in");
- ofstream fout("maze.out");
- vector<vector<int>> labir;
- vector<vector<pair<int, int>>> predki;
- int M, N;
- fin >> M >> N;
- labir.resize(M);
- predki.resize(M);
- for (int i = 0; i < M; i++)
- {
- labir[i].resize(N);
- predki[i].resize(N);
- }
- pair<int, int> begin;
- pair<int, int> end;
- fin >> begin.first >> begin.second;
- fin >> end.first >> end.second;
- end.first = end.first - 1;
- end.second = end.second - 1;
- begin.first = begin.first - 1;
- begin.second = begin.second - 1;
- for (int i = 0; i < M; i++)
- {
- for (int j = 0; j < N; j++)
- {
- int b;
- fin >> b;
- if (b == 1)
- {
- labir[i][j] = 0;
- }
- else
- {
- labir[i][j] = -1;
- }
- }
- }
- queue<pair<int, int>> obhod;
- obhod.push(begin);
- while (labir[end.first][end.second] == 0 && !obhod.empty())
- {
- pair<int, int> t;
- t = obhod.front();
- obhod.pop();
- func(obhod, predki, labir, t, begin.first, begin.second);
- }
- if (labir[end.first][end.second] == 0)
- {
- fout << -1;
- }
- else
- {
- fout << labir[end.first][end.second] << endl;
- pair<int, int> t1 = end;
- pair<int, int> t2;
- deque<pair <int, int>> way;
- for (int i = 0; i < labir[end.first][end.second]; i++)
- {
- t2 = predki[t1.first][t1.second];
- t1 = t2;
- way.push_front(t2);
- }
- for (int i = 0; i < labir[end.first][end.second]; i++)
- {
- fout << way.front().first + 1 << " " << way.front().second + 1 << endl;
- way.pop_front();
- }
- fout << end.first + 1 << " " << end.second + 1 << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement