Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <queue>
- #include "Cell.hpp"
- template<typename T>
- T** makeMatrix(const size_t N)
- {
- T** matrix = new T*[N];
- for (int i = 0; i < N; ++i)
- matrix[i] = new T[N];
- return matrix;
- }
- template<typename T>
- void printMatrix(T** matrix, const size_t N)
- {
- for (int i = 0; i < N; ++i)
- {
- for (int j = 0; j < N; ++j)
- {
- std::cout << matrix[i][j] << ' ';
- }
- std::cout << std::endl;
- }
- }
- void markAsVisited(bool** visitedMatrix, const int i, const int j)
- {
- visitedMatrix[i][j] = 1;
- }
- void setCellsValues(char** inputMatrix, bool** visitedMatrix, const size_t N)
- {
- for (int i = 0; i < N; ++i)
- {
- for (int j = 0; j < N; ++j)
- {
- std::cin >> inputMatrix[i][j];
- if (inputMatrix[i][j] == 'X')
- markAsVisited(visitedMatrix, i, j);
- }
- }
- }
- bool possibleUP(const int x, const int y,bool** visitedMatrix)
- {
- return x - 1 >= 0 && visitedMatrix[x - 1][y] != 1;
- }
- bool possibleDown(const int x,const int y,bool** visitedMatrix,const size_t N)
- {
- return x + 1 < N && visitedMatrix[x + 1][y] != 1;
- }
- bool possibleLeft(const int x, const int y, bool** visitedMatrix)
- {
- return y - 1 >= 0 && visitedMatrix[x][y - 1] != 1;
- }
- bool possibleRight(const int x, const int y, bool** visitedMatrix, const size_t N)
- {
- return y + 1 < N && visitedMatrix[x][y + 1] != 1;
- }
- void move(std::queue<Cell>& cellsQueue, bool** visitedMatrix, const int x, const int y, const int dist)
- {
- cellsQueue.push(Cell(x, y, dist));
- markAsVisited(visitedMatrix, x, y);
- }
- int main()
- {
- size_t N;
- std::cin >> N;
- char** inputMatrix = makeMatrix<char>(N);
- bool** visitedMatrix = makeMatrix<bool>(N);
- setCellsValues(inputMatrix, visitedMatrix, N);
- int xStart, yStart, xEnd, yEnd;
- std::cin >> xStart >> yStart >> xEnd >> yEnd;
- Cell start(xStart, yStart);
- std::queue<Cell> cellsQueue;
- cellsQueue.push(start);
- markAsVisited(visitedMatrix, start.x, start.y);
- while (!cellsQueue.empty())
- {
- Cell c = cellsQueue.front();
- cellsQueue.pop();
- if (c.x == xEnd && c.y == yEnd)
- return c.dist;
- //go up
- if (possibleUP(c.x, c.y, visitedMatrix))
- move(cellsQueue, visitedMatrix, c.x - 1, c.y, c.dist + 1);
- //go down
- if (possibleDown(c.x, c.y, visitedMatrix, N))
- move(cellsQueue, visitedMatrix, c.x + 1, c.y, c.dist + 1);
- //go left
- if (possibleLeft(c.x, c.y, visitedMatrix))
- move(cellsQueue, visitedMatrix, c.x, c.y -1 , c.dist + 1);
- //go right
- if (possibleRight(c.x,c.y,visitedMatrix,N))
- move(cellsQueue, visitedMatrix, c.x, c.y + 1, c.dist + 1);
- }
- return -1;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement