#include <vector>
#include <iostream>

using namespace std;
void PrintVV(vector<vector<int> > &dp)
{
    for (int i = 0; i < dp.size(); ++i)
    {
        for (int j = 0; j < dp[i].size(); ++j)
        {
            cout<< dp[i][j] << ',';
        }
        cout << '\n';
    }
	
    cout << endl;
}

int UniquePathsWithObstacles(vector<vector<int> > &dp) 
{
    if (dp.back().back() == 1) return 0;

    int r = dp.size();
    int c = dp[0].size();
	
	dp.back().back() = 1;
	
	//initialize last row
    for (int i = c-2; i >= 0; --i)
        dp[r-1][i] = (dp[r-1][i]==0?1:0) & dp[r-1][i+1];

	//initialize last column
    for (int j = r-2; j >= 0; --j)
        dp[j][c-1] = (dp[j][c-1]==0?1:0) & dp[j+1][c-1];

	//calculate each inside cells
    for (int i = r-2; i >=0; --i)
        for (int j = c-2; j >=0; --j)
            dp[i][j] = dp[i][j]==0?(dp[i+1][j] + dp[i][j+1]):0;

    return dp[0][0];
}



int main(int argc, char** argv)
{
    vector<vector<int> > path(3);

    path[0].push_back(0);
    path[0].push_back(0);
    path[0].push_back(0);
    path[1].push_back(0);
    path[1].push_back(1);
    path[1].push_back(0);
    path[2].push_back(0);
    path[2].push_back(0);
    path[2].push_back(0);
	PrintVV(path);
    cout << UniquePathsWithObstacles(path);
    return 0;
}