# Return number of paths to an exit in matrix maze

My task is to check if we can get from Starting Position to exit(there can be multiple exits) and to display amount of steps of shortest path.

S-Starting postion

O-Walkable space

X-Wall (can’t walk through it)

W-Exit

I managed to get above part to work but theres still 1 more thing to do, I have to check if exit has any alternate paths. So even if shortest path to exit_A is 3, I need to find out if there’s any other way to exit, even if it takes 15 steps to go there,

So in short, is there a smart way to edit code posted below to also display number of all possible Alternate Paths? (Alternate Path must differ from original with atleast 1 connection)

Find shortest path algorithm:

``struct Point {     int x;     int y; };   struct queueNode {     Point pt;       int dist;   };   bool isValid(int row, int col) {      return (row >= 0) && (row < ROW) &&            (col >= 0) && (col < COL); }  int rowNum[] = {-1, 0, 0, 1}; int colNum[] = {0, -1, 1, 0};   int BFS(int mat[][COL], Point src, Point dest) {     if (!mat[src.x][src.y] || !mat[dest.x][dest.y])         return -1;      bool visited[ROW][COL];     memset(visited, false, sizeof visited);       visited[src.x][src.y] = true;      queue<queueNode> q;       queueNode s = {src, 0};     q.push(s);         while (!q.empty())     {         queueNode curr = q.front();         Point pt = curr.pt;           if (pt.x == dest.x && pt.y == dest.y)             return curr.dist;          q.pop();          for (int i = 0; i < 4; i++)         {             int row = pt.x + rowNum[i];             int col = pt.y + colNum[i];               if (isValid(row, col) && mat[row][col] &&                     !visited[row][col])             {                  visited[row][col] = true;                 queueNode Adjcell = { {row, col},                     curr.dist + 1                 };                 q.push(Adjcell);             }         }     }       return -1; } ``

Main:

``int main() {     int Exits;     int Sr, Sc, r, c;      int mat[ROW][COL] =     {         { 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },         { 1, 0, 1, 0, 1, 1, 1, 0, 1, 1 },         { 1, 1, 1, 0, 1, 1, 0, 1, 0, 1 },         { 0, 0, 0, 0, 1, 0, 0, 0, 0, 1 },         { 1, 1, 1, 0, 1, 1, 1, 0, 1, 0 },         { 1, 0, 1, 1, 1, 1, 0, 1, 0, 0 },         { 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 },         { 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },         { 1, 1, 0, 0, 0, 0, 1, 0, 0, 1 }     };       cout<<" Set Starting Position [row] [col]: "<<endl;     cin >> Sr;     cin >> Sc;     Point source = {Sr, Sc};      cout<<"Number of Exits: "<<endl;     cin >> Exits;;     int Steps[Exits];     int MemR[Exits];     int MemC[Exits];     int Best_Path;     int Best_Point;    for (int b = 0; b < Exits; b++)     {     Steps[b]=0;     }      for (int i=0; i<Exits; i++)     {         cout<<"Type in coordinates for Exit nr."<<i+1<<endl;         cin >> r;         cin >> c;         MemR[i]=r;         MemC[i]=c;          mat[r][c]=2; //Dzięki temu Wyjścia są traktowane jako droga.      }   cout<<"==========LABIRYNTH: =========="<<endl<<endl;    cout << "  ";  for (int z = 0; z < COL; z++)     {         cout<<z<<"  ";     }     cout<<endl;      for (int t = 0; t < ROW; t++)     {         cout<<t<<" ";          for (int u = 0; u < COL; u++)         {             if (t==Sr && u==Sc)                 cout << "S " << ' ';          else if (mat[t][u]==2)               {                   cout << "W " << ' ';               }       else             {                 if (mat[t][u]==0)                     cout << "X " << ' ';                 if (mat[t][u]==1)                     cout << "O " << ' ';             }             }         cout << endl;     }  cout<<endl<<"==========PATHS: =========="<<endl<<endl;  for (int j=0; j<Exits; j++) {      Point dest = {MemR[j], MemC[j]};     int dist = BFS(mat, source, dest);      if (dist != INT_MAX && dist != -1)     {         Steps[j]=dist;         cout << "Shortest path to poin ["<<MemR[j]<<"] " <<"["<<MemC[j]<<"] equals "<<dist<<" steps"<<endl;     }       else if (dist= -1)         cout << "No path or exit is equal to 0 for point: ["<<MemR[j]<<"] " <<"["<<MemC[j]<<"]"<<endl;     else         cout << "No path for point: ["<<MemR[j]<<"] " <<"["<<MemC[j]<<"]"<<endl;  }  cout<<endl<<"==========Best route: =========="<<endl<<endl; Best_Path = Steps[0]; for (int n = 0; n < Exits; n++) {     if (Best_Path > Steps[n] && Steps[n]!=0)          Best_Path = Steps[n]; }    for (int z=0; z<Exits; z++) {     if (Steps[z]==Best_Path && Best_Path!=0)     {         cout <<"Best route exists for point: ["<<MemR[z]<<"] " <<"["<<MemC[z]<<"] and equals "<<Best_Path<<" steps"<<endl;     }  }     return 0; } ``