左右中只能选一个方向，若选择左只能一直向左走。上下中只能选择一个方向，若选择下只能一直向下。
所以有2种情况
（1）二者位置在对角线上
（2）两者位置重合或处于同一行或同一列
class Visit {
public:
int countPath(vector<vector<int> > map, int n, int m) {
// write code here
int si,sj,ei,ej,dp[12][12];
memset(dp,0,sizeof(dp));
for(int i=0;i<n;i++)
for(int j=0;j<m;j++){
if(map[i][j]==1){si=i;sj=j;}
if(map[i][j]==2){ei=i;ej=j;}
}
//同行或同列 //这里应该还能优化到下面的对角线那种情况（懒）
if(si==ei){
for(int i=min(sj,ej);i<=max(sj,ej);i++)
if(map[si][i]==-1)
return 0;
return 1;
}
if(sj==ej){
for(int i=min(si,ei);i<=max(si,ei);i++)
if(map[i][sj]==-1)
return 0;
return 1;
}
//对角线 //裸的动态规划
if(si>ei) {swap(si,ei);swap(sj,ej);}
int g=1;if(sj>ej) g=-1;
for(int i=si+1;i<=ei;i++){
if(map[i][sj]==0) dp[i][sj]=1;
else break;
}
for(int j=sj+g;;j+=g){
if(sj>ej){
if(j==-1) break;
}
else{
if(j==ej+1) break;
}
if(map[si][j]==0) dp[si][j]=1;
else break;
}
for(int i=si+1;i<=ei;i++){
for(int j=sj+g;;j+=g){
if(sj>ej){
if(j==-1) break;
}
else{
if(j==ej+1) break;
}
dp[i][j]=dp[i-1][j]+dp[i][j-g];
cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
}
}
return dp[ei][ej];
}
};