I would like to make a function, which can give the coordinates of the possible pathes between two elements in a simple matrix. Until now, I have managed to determine, whether there could be a path between the two, however, I am pulling my hair out to determine the coordinate of pathes. I was thinking about a linked list, where the pointers is pointing to the next reachable, neighbouring element. However, I feel, that there should be a much simplier method to do that.
Update 1:
I started to create the solution according to sp2danny comment, but unfortunately, it gives me really weird errors in conncetion with unvisitedNeighbours:
unvisitedNeighbours[0].pMain=error: type 'std::queue<node,std::deque<node,std::allocator > >' does not provide a subscript operator
and there is an another error:
this->parent->parent->parent.parent.parent= error: invalid use of 'this' outside of a non-static member function
the errors happen just after pushing the src element to the queue.
#include <vector>
#include <iostream>
#include <queue>
using namespace std;
#define row 5
#define col 5
struct node {
pair<int, int> pMain;
pair<int, int> parent;
int index;
node(pair<int, int> _p, pair<int, int> _parent, int _index) {
pMain = _p;
parent = _parent;
int index = _index;
}
};
// to find the path from
// top left to bottom right
bool isPath(int arr[row][col]) {
// directions
int dir[4][2] = {{0, 1},{0, -1},{1, 0},{-1, 0}};
// queue
queue<node> unvisitedNeighbours;
// insert the top right corner.
node Node(node(make_pair(0, 0), make_pair(-1, -1), 0));
unvisitedNeighbours.emplace(Node);
std::vector<node> pathes;
pathes.push_back(Node);
// until queue is empty
while (!unvisitedNeighbours.empty()) {
node p = unvisitedNeighbours.front();
unvisitedNeighbours.pop();
// mark as visited
arr[p.pMain.first][p.pMain.second] = -1;
// destination is reached.
if (p.pMain == make_pair(row - 1, col - 1)) {
int index = p.index;
while (index != 0) {
std::cout << pathes.at(index).pMain.first << " " << pathes.at(index).pMain.second << endl;
index = pathes.at(index).index;
}
return true;
}
// check all four directions
for (int i = 0; i < 4; i++) {
// using the direction array
int a = p.pMain.first + dir[i][0];
int b = p.pMain.second + dir[i][1];
// not blocked and valid
if (arr[a][b] != -1 && a >= 0 && b >= 0
&& a < row && b < col) {
pathes.push_back(node(make_pair(a, b), p.pMain, pathes.size() - 1));
unvisitedNeighbours.push(node(make_pair(a, b), p.pMain, pathes.size() - 1));
}
}
}
return false;
}
// Driver Code
int main() {
// Given array
int arr[row][col] = {{0, 0, 0, -1, 0},
{-1, 0, 0, -1, -1},
{0, 0, 0, -1, 0},
{-1, 0, 0, 0, 0},
{0, 0, -1, 0, 0}};
// path from arr[0][0] to arr[row][col]
if (isPath(arr))
cout << "Yes";
else
cout << "No";
return 0;
}
Basically, you're trying to find the shortest path of an unweighted graph. Here the graph is a 2D grid.
To print the path, you just need to keep track of the nodes and their parent nodes when you're visiting them.
Here's a sample code:
#include<iostream>
#include<vector>
#include<queue>
#include<map>
using namespace std;
int dirX[] = {-1, 0, 0, 1};
int dirY[] = {0, -1, 1, 0};
bool IsValid(int& r, int& c, int &totalRow, int& totalCol)
{
return (r >= 0 && r < totalRow && c >= 0 && c < totalCol);
}
int BFS(vector<vector<int>>& grid, pair<int, int> source, pair<int, int> destination, map<pair<int, int>, pair<int, int>>& parent)
{
int totalRow = grid.size();
int totalCol = grid[0].size();
vector<vector<int>> visited(totalRow, vector<int> (totalCol, 0));
vector<vector<int>> level(totalRow, vector<int> (totalCol, 0));
queue<pair<int, int>> q;
q.push(source);
parent[source] = { -1, -1 };
while (!q.empty())
{
pair<int, int> curr = q.front();
q.pop();
visited[curr.first][curr.second] = true;
for (int d = 0; d < 4; d++)
{
int nextR = curr.first + dirX[d];
int nextC = curr.second + dirY[d];
if (IsValid(nextR, nextC, totalRow, totalCol) && grid[nextR][nextC] != -1 && !visited[nextR][nextC])
{
level[nextR][nextC] = 1 + level[curr.first][curr.second];
visited[nextR][nextC] = true;
parent[{nextR, nextC}] = curr;
q.push({nextR, nextC});
if (make_pair(nextR, nextC) == destination)
{
return level[nextR][nextC];
}
}
}
}
return -1;
}
void PrintShortestPath(vector<vector<int>> &grid, pair<int, int> source, pair<int, int> destination)
{
map<pair<int, int>, pair<int, int>> parent;
int shortestDistance = BFS(grid, source, destination, parent);
if (shortestDistance == -1)
{
cout << "No path available!" << endl;
}
else
{
vector<pair<int, int>> path;
pair<int, int> currentNode = destination;
path.push_back(destination);
cout << "Shortest distance: " << shortestDistance << endl;
while (parent[currentNode] != make_pair(- 1, -1))
{
path.push_back(parent[currentNode]);
currentNode = parent[currentNode];
}
for (auto &curr : path)
{
cout << curr.first << " " << curr.second << endl;
}
}
}
int main()
{
vector<vector<int>> grid
{
{0, 0, 0, -1, 0},
{-1, 0, 0, -1, -1},
{0, 0, 0, -1, 0},
{-1, 0, 0, 0, 0},
{0, 0, -1, 0, 0}
};
PrintShortestPath(grid, { 0, 0 }, { 4, 4 });
}
Note: If you search in google "Print shortest path of an unweighted graph", you'll be able to find more about it.
In the constructor, you've written int index = _index. Due to this, the correct index value was not assigned.
So at the time of accessing pathes.at(index), the error occurred.
node(pair<int, int> _p, pair<int, int> _parent, int _index)
{
pMain = _p;
parent = _parent;
index = _index;
}