Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<fstream>
- #include<queue>
- #include<stack>
- #include<vector>
- using namespace std;
- int main()
- {
- fstream fin("maze.in");
- ofstream fout("maze.out");
- int N, M;
- int X1, X2, Y1, Y2;
- fin >> N >> M;
- fin >> X1 >> Y1;
- fin >> X2 >> Y2;
- if (X1==X2 && Y1==Y2)
- {
- fout << "0" << endl;
- fout << X1 << " " << Y1;
- return 0;
- }
- X1--; X2--; Y1--; Y2--;
- vector < vector < int>> labirint(N, vector<int>(M));
- for (int i = 0; i < N; i++)
- {
- for (int j = 0; j < M; j++)
- {
- fin >> labirint[i][j];
- }
- }
- vector < vector < int>> cells_visited(N, vector<int>(M));
- cells_visited[X1][Y1] = 1;
- vector<vector<pair<int, int>>>
- way(N, vector < pair<int, int>>
- (M, make_pair(-1, -1)));
- queue<pair<int, int>>queue;
- queue.push(make_pair (X1, Y1));
- while (!queue.empty())
- {
- int value1 = queue.front().first;
- int value2 = queue.front().second;
- queue.pop();
- if (value1+1 < N)
- {
- if (labirint[value1+1][value2]!=0)
- {
- if (!cells_visited[value1 + 1][value2])
- {
- cells_visited[value1 + 1][value2] = 1;
- way[value1 + 1][value2] = make_pair(value1 , value2);
- queue.push(make_pair(value1 + 1, value2));
- }
- }
- }
- if (value2 + 1 < M)
- {
- if (labirint[value1][value2+1] != 0)
- {
- if (!cells_visited[value1][value2+1])
- {
- cells_visited[value1][value2+1] = 1;
- way[value1][value2+1] = make_pair(value1, value2);
- queue.push(make_pair(value1, value2+1));
- }
- }
- }
- if (value1 - 1 >= 0)
- {
- if (labirint[value1-1][value2] != 0)
- {
- if (!cells_visited[value1 -1][value2])
- {
- cells_visited[value1 - 1][value2] = 1;
- way[value1 - 1][value2] = make_pair(value1, value2);
- queue.push(make_pair(value1 - 1, value2));
- }
- }
- }
- if (value2 - 1 >= 0)
- {
- if (labirint[value1][value2-1] != 0)
- {
- if (!cells_visited[value1][value2-1])
- {
- cells_visited[value1][value2-1] = 1;
- way[value1][value2-1] = make_pair(value1, value2);
- queue.push(make_pair(value1, value2-1));
- }
- }
- }
- }
- if (way[X2][Y2].first == -1)
- {
- fout << "-1"<<endl;
- }
- else
- {
- stack<pair<int, int>> final_way;
- for (int valueX2 = X2, valueY2 = Y2; ; )
- {
- if (valueX2 == X1 && valueY2 == Y1)
- {
- break;
- }
- final_way.push(make_pair(valueX2 + 1, valueY2 + 1));
- int variable = valueX2;
- valueX2 = way[valueX2][valueY2].first;
- valueY2 = way[variable][valueY2].second;
- }
- final_way.push(make_pair(X1 + 1, Y1 + 1));
- int way_size = final_way.size();
- fout << way_size - 1 << endl;
- while (!final_way.empty())
- {
- fout << final_way.top().first << " " << final_way.top().second << endl;
- final_way.pop();
- }
- }
- fin.close();
- fout.close();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement