Minimum number of flips required such that a Binary Matrix doesn’t contain any path from the top left to the bottom right consisting only of 0s

  

#include "bits/stdc++.h"

using namespace std;

  

int direction[][2] = { { -1, 0 }, { 0, 1 }, 

                       { 0, -1 }, { 1, 0 } };

  

bool dfs(vector<vector<int> >& matrix,

         int i, int j, int N, int M)

{

  

    

    

    if (i == N - 1 and j == M - 1) {

        return true;

    }

  

    

    matrix[i][j] = 1;

  

    

    for (int k = 0; k < 4; k++) {

  

        

        int newX = i + direction[k][0];

        int newY = j + direction[k][1];

  

        

        if (newX >= 0 and newX < N

            and newY >= 0 and newY < M

            and matrix[newX][newY] == 0) {

  

            

            if (dfs(matrix, newX,

                    newY, N, M)) {

  

                

                

                return true;

            }

        }

    }

  

    

    

    return false;

}

  

int solve(vector<vector<int> >& matrix)

{

  

    int N = matrix.size();

    int M = matrix[0].size();

  

    

    

    if (!dfs(matrix, 0, 0, N, M)) {

        return 0;

    }

  

    

    

    if (!dfs(matrix, 0, 0, N, M)) {

        return 1;

    }

  

    

    return 2;

}

  

int main()

{

    vector<vector<int> > mat = {

        { 0, 1, 0, 0 },

        { 0, 1, 0, 0 },

        { 0, 0, 0, 0 }

    };

    cout << solve(mat);

  

    return 0;

}

Adblock test (Why?)

Original page link

Best Cool Tech Gadgets

Top favorite technology gadgets