Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <limits.h>
- #include <math.h>
- #include <string>
- using namespace std;
- class Point2D
- {
- public:
- int r;
- int c;
- Point2D()
- {
- }
- Point2D(const Point2D &input)
- {
- r = input.r;
- c = input.c;
- }
- Point2D(int y, int x)
- {
- r = y;
- c = x;
- }
- string content()
- {
- return "(" + to_string(r) + ", " + to_string(c) + ")";
- }
- };
- class Adj
- {
- public:
- Point2D root;
- vector<Point2D> childs;
- string content()
- {
- string str;
- str = root.content() + ": ";
- for (int i = 0; i < childs.size(); i++)
- {
- str = str + childs[i].content() + " -> ";
- }
- return str;
- }
- };
- vector<vector<int>> getMaze(Point2D maze_size)
- {
- vector<vector<int>> maze;
- char temp;
- for (int r = 0; r < maze_size.r; r++)
- {
- vector<int> row;
- for (int c = 0; c < maze_size.c; c++)
- {
- cin >> temp;
- row.push_back(atoi(&temp));
- }
- maze.push_back(row);
- }
- return maze;
- }
- Point2D getStartPoint(vector<vector<int>> &maze)
- {
- for (int r = 0; r < maze.size(); r++)
- {
- for (int c = 0; c < maze.size(); c++)
- {
- if (maze[r][c] == 2)
- {
- return Point2D(r, c);
- }
- }
- }
- }
- Point2D getEndPoint(vector<vector<int>> &maze)
- {
- for (int r = 0; r < maze.size(); r++)
- {
- for (int c = 0; c < maze.size(); c++)
- {
- if (maze[r][c] == 3)
- {
- return Point2D(r, c);
- }
- }
- }
- }
- bool isWall(vector<vector<int>> &maze, Point2D target)
- {
- //check is out of maze
- if (target.r < 0 || target.c < 0)
- {
- return true;
- }
- if (target.r >= maze.size() || target.c >= maze[0].size())
- {
- return true;
- }
- //check is wall
- if (maze[target.r][target.c] == 1)
- {
- return true;
- }
- return false;
- }
- bool isExist(vector<Adj> list, Point2D target)
- {
- for (int i = 0; i < list.size(); i++)
- {
- if (list[i].root.c == target.c && list[i].root.r == target.r)
- {
- return true;
- }
- }
- return false;
- }
- vector<Point2D> getChilds(vector<vector<int>> &maze, Point2D target)
- {
- vector<Point2D> output;
- Point2D up(target.r-1, target.c);
- Point2D down(target.r+1, target.c);
- Point2D left(target.r, target.c-1);
- Point2D right(target.r, target.c+1);
- if (!isWall(maze, up))
- {
- output.push_back(up);
- }
- if (!isWall(maze, down))
- {
- output.push_back(down);
- }
- if (!isWall(maze, left))
- {
- output.push_back(left);
- }
- if (!isWall(maze, right))
- {
- output.push_back(right);
- }
- return output;
- }
- bool goMaze(vector<vector<int>> &maze, Point2D point_start, Point2D point_end)
- {
- /*for (int r = 0; r < maze.size(); r++)
- {
- for (int c = 0; c < maze.size(); c++)
- {
- cout << maze[r][c] << ", ";
- }
- cout << endl;
- }*/
- //cout <<"Start" << point_start.content() << endl;
- //cout << "End" << point_end.content() << endl;
- Adj firstAdj;
- firstAdj.root = point_start;
- firstAdj.childs = getChilds(maze, firstAdj.root);
- //cout << "FisrtAdj: " << firstAdj.content() << endl;
- vector<Adj> adjList;
- adjList.push_back(firstAdj);
- for (int finger = 0; finger < adjList.size(); finger++)
- {
- //cout << "Current: " << adjList[finger].content() << endl;
- Adj current = adjList[finger];
- if (current.root.r == point_end.r && current.root.c == point_end.c)
- {
- return true;
- }
- for (int i = 0; i < current.childs.size(); i++)
- {
- if (!isExist(adjList, current.childs[i])) //check is already in list;
- {
- Adj newAdj;
- newAdj.root = current.childs[i];
- newAdj.childs = getChilds(maze, newAdj.root);
- adjList.push_back(newAdj);
- }
- }
- }
- return false;
- }
- int main()
- {
- Point2D maze_size;
- maze_size = Point2D(16, 16);
- //cout << "Maze size: " << maze_size.content() << endl;
- int temp;
- while (cin >> temp)
- {
- //cout << temp << ", " << endl;
- vector<vector<int>> curr_maze = getMaze(maze_size);
- Point2D point_start = getStartPoint(curr_maze);
- Point2D point_end = getEndPoint(curr_maze);
- bool suc = goMaze(curr_maze, point_start, point_end);
- cout << "#" << temp;
- if (suc)
- {
- cout << " 1" << endl;
- }
- else
- {
- cout << " 0" << endl;
- }
- }
- //cout << "hello world" << endl;
- getchar();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement