bool isValidCell(int x, int y)
{
    if (x < 0 || y < 0 || x >= ROW || y >= COL)
        return false;

    return true;
}

void countPaths(int mat[ROW][COL], int x, int y, int visited[ROW][COL], int& count)
{
    if (x == ROW - 1 && y == COL - 1)
    {
        count++;
        return;
    }


    visited[x][y] = 1;
    if (isValidCell(x, y) && mat[x][y])
    {

        if (x + 1 < ROW && !visited[x + 1][y])
            countPaths(mat, x + 1, y, visited, count);


        if (x - 1 >= 0 && !visited[x - 1][y])
            countPaths(mat, x - 1, y, visited, count);


        if (y + 1 < COL && !visited[x][y + 1])
            countPaths(mat, x, y + 1, visited, count);


        if (y - 1 >= 0 && !visited[x][y - 1])
            countPaths(mat, x, y - 1, visited, count);
    }


    visited[x][y] = 0;
}

int visited[ROW][COL];
    memset(visited, 0, sizeof visited);
    countPaths(mat, 0, 0, visited, count);

    cout << "Number of unique paths are " << count<<endl;

#include <bits/stdc++.h>
#include <iostream>
#define ROW 9
#define COL 10

using namespace std;




struct Point
{
    int x;
    int y;
};


struct queueNode
{
    Point pt;
    int dist;
};


bool isValidCell(int x, int y)
{
    if (x < 0 || y < 0 || x >= ROW || y >= COL)
        return false;

    return true;
}

void countPaths(int mat[ROW][COL], int x, int y, int visited[ROW][COL], int& count)
{
    if (x == ROW - 1 && y == COL - 1)
    {
        count++;
        return;
    }


    visited[x][y] = 1;
    if (isValidCell(x, y) && mat[x][y])
    {

        if (x + 1 < ROW && !visited[x + 1][y])
            countPaths(mat, x + 1, y, visited, count);


        if (x - 1 >= 0 && !visited[x - 1][y])
            countPaths(mat, x - 1, y, visited, count);


        if (y + 1 < COL && !visited[x][y + 1])
            countPaths(mat, x, y + 1, visited, count);


        if (y - 1 >= 0 && !visited[x][y - 1])
            countPaths(mat, x, y - 1, visited, count);
    }


    visited[x][y] = 0;
}





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 (isValidCell(row, col) && mat[row][col] &&
                    !visited[row][col])
            {

                visited[row][col] = true;
                queueNode Adjcell = { {row, col},
                    curr.dist + 1
                };
                q.push(Adjcell);
            }
        }
    }


    return -1;
}

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 point ["<<MemR[j]<<"] " <<"["<<MemC[j]<<"] equals "<<dist<<" steps"<<endl;
            int count = 0;


            int visited[ROW][COL];
            memset(visited, 0, sizeof visited);
            countPaths(mat, 0, 0, visited, count);

            cout << "Number of unique paths are " << count<<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;
}