#include<iostream>
#include<time.h>
#include<string.h>
using namespace std;

//question 4 and 5

 int uniquePathsWithObstacles(int** obstacleGrid, int m, int n){
    // Cas extrêmes : départ ou arrivée bloqués
    if(obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1){
        return 0;
    }

    // Tableau 1D : dp[j] = nombre de chemins vers la case courante (i,j)
    int* dp = new int[n];

    // Initialisation de la première ligne
    dp[0] = 1;
    for(int j = 1; j < n; j++){
        dp[j] = (obstacleGrid[0][j] == 1) ? 0 : dp[j-1];
    }

    // Lignes suivantes
    for(int i = 1; i < m; i++){
        // Première colonne de la ligne i
        dp[0] = (obstacleGrid[i][0] == 1) ? 0 : dp[0];

        for(int j = 1; j < n; j++){
            if(obstacleGrid[i][j] == 1){
                dp[j] = 0;
            } else {
                dp[j] = dp[j] + dp[j-1];  // haut + gauche
            }
        }
    }

    int result = dp[n-1];
    delete[] dp;
    return result;
}


}

int main(){
    int m = 1;
    int n = 2;
    int obs[m][n] = {{0,1}};//obstacles array
    //convert obstacles array to int **
    int * p[m];
    for(int i = 0; i<m; i++) p[i] = obs[i];

    int r = uniquePathsWithObstacles(p, m, n);
    cout<<r<<endl;
}

//test case used: 
//m, n      obs                              result      
//3,3       [[0,0,0],[0,1,0],[0,0,0]]           2
//1,2       [[0,1]]                             0     
//3,2       [[0,0],[1,1],[0,0]]                 0   
//1,1       [[1]]                               0