Check if a path exists from a given cell to any boundary element of the Matrix with sum of elements not exceeding K

#include <bits/stdc++.h>

using namespace std;

  

bool isValid(vector<vector<int> >& board,

             int i, int j, int K)

{

    if (board[i][j] <= K) {

        return true;

    }

  

    

    return false;

}

  

bool findPath(vector<vector<int> >& board,

              int X, int Y,

              int M, int N, int K)

{

  

    

    if (X < 0 || X == M

        || Y < 0 || Y == N) {

        return true;

    }

  

    

    if (isValid(board, X, Y, K)) {

  

        

        int board_XY = board[X][Y];

  

        

        board[X][Y] = INT_MAX;

  

        

        if (findPath(board, X + 1, Y, M,

                     N, K - board_XY)

            || findPath(board, X - 1, Y, M,

                        N, K - board_XY)

            || findPath(board, X, Y + 1, M,

                        N, K - board_XY)

            || findPath(board, X, Y - 1, M,

                        N, K - board_XY)) {

            return true;

        }

  

        

        board[X][Y] = board_XY;

    }

  

    

    return false;

}

  

int main()

{

    vector<vector<int> > grid = {

        { 25, 5, 25, 25, 25, 25 },

        { 25, 1, 1, 5, 12, 25 },

        { 25, 1, 12, 0, 15, 25 },

        { 22, 1, 11, 2, 19, 15 },

        { 25, 2, 2, 1, 12, 15 },

        { 25, 9, 10, 1, 11, 25 },

        { 25, 25, 25, 25, 25, 25 }

    };

  

    int K = 17;

    int M = grid.size();

    int N = grid[0].size();

    int X = 2, Y = 3;

  

    if (findPath(grid, X, Y, M, N, K))

        cout << "Yes";

    else

        cout << "No";

  

    return 0;

}

Let's block ads! (Why?)

Original page link

Best Cool Tech Gadgets

Top favorite technology gadgets