Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <queue>
- #include <fstream>
- #include <vector>
- #include <stack>
- struct coord{
- unsigned int x, y;
- };
- void check (std::vector<std::vector<coord>> &last, std::queue<coord> &qu, std::vector<std::vector<char>> &maze, int x, int y, coord &coordinate) {
- last[x][y] = coordinate;
- coord temp;
- temp.x = x;
- temp.y = y;
- qu.push(temp);
- maze[x][y] = '+';
- }
- int main() {
- unsigned int n, x, y;
- coord start, finish, coordinate;
- std::vector<std::vector<char>> maze;
- std::vector<std::vector<coord>> last;
- std::ifstream inp("input.txt");
- inp >> n >> start.y >> start.x >> finish.x >> finish.y;
- maze.resize(n);
- last.resize(n);
- for (int i = 0; i < n; ++i) {
- maze[i].resize(n);
- last[i].resize(n);
- }
- for (int i = 0; i < n; ++i) {
- for (int j = 0; j < n; ++j) {
- inp >> maze[i][j];
- }
- }
- inp.close();
- start.x--;
- start.y--;
- finish.x--;
- finish.y--;
- std::stack<coord> path;
- std::queue<coord> qu;
- maze[start.x][start.y] = '+';
- coordinate.x = start.x;
- coordinate.y = start.y;
- qu.push(coordinate);
- while (!qu.empty()) {
- coordinate = qu.front();
- x = coordinate.x;
- y = coordinate.y;
- qu.pop();
- if (coordinate.x == finish.y && coordinate.y == finish.x) {
- break;
- }
- if (x > 0 && maze[x - 1][y] == '.') {
- check(last, qu, maze, x-1, y, coordinate);
- }
- if (x < n - 1 && maze[x + 1][y] == '.') {
- check(last, qu, maze, x+1, y, coordinate);
- }
- if (y > 0 && maze[x][y - 1] == '.') {
- check(last, qu, maze, x, y-1, coordinate);
- }
- if (y < n - 1 && maze[x][y + 1] == '.') {
- check(last, qu, maze, x, y+1, coordinate);
- }
- }
- while (coordinate.x != start.x || coordinate.y != start.y) {
- path.push(coordinate);
- coordinate = last[coordinate.x][coordinate.y];
- }
- int res = 0;
- res = path.size();
- std::ofstream outp("output.txt");
- outp << res;
- outp.close();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement