/*** @author Limg* @date 2022/08/09* 一個機器人位于一個 m x n 網格的左上角 （起始點在下圖中標記為 “Start” ）。* 機器人每次只能向下或者向右移動一步。機器人試圖達到網格的右下角（在下圖中標記為 “Finish”）。* 現在考慮網格中有障礙物。那么從左上角到右下角將會有多少條不同的路徑？* 網格中的障礙物和空位置分別用 1 和 0 來表示。
*/
#include<iostream>
#include<vector>
using namespace std;
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid);
int main()
{int m=2,n=2;cin>>m;cin>>n;vector<vector<int> > obstacleGrid;int value;vector<int> temp;  for(int i=0;i<m;i++){for(int j=0;j<n;j++){cin>>value;temp.push_back(value);}obstacleGrid.push_back(temp);temp.clear();}cout<<uniquePathsWithObstacles(obstacleGrid)<<endl;return 0;
}
//解題函數
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) 
{int m = obstacleGrid.size();int n = obstacleGrid[0].size();long record[m][n];if(obstacleGrid[0][0]==1){record[0][0]=0;}else{record[0][0]=1;}for(int i=1;i<m;i++)   {if(obstacleGrid[i][0]==1){record[i][0]=0;}else{record[i][0]=record[i-1][0];}  }for(int i=1;i<n;i++){if(obstacleGrid[0][i]==1){record[0][i]=0;}else{record[0][i]=record[0][i-1];    //這里注意!!要考慮前面有障礙物后面都不通}}for(int i=1;i<m;i++){for(int j=1;j<n;j++){if(obstacleGrid[i][j]==1){record[i][j]=0;}else{record[i][j]=record[i-1][j]+record[i][j-1];}}}return record[m-1][n-1];
}