Going from the point (x1,y1) to the point (x2,y2) in the Cartesian graph takes at least |x1−x2|+|y1−y2| steps moving unit length along the x-axis or the y-axis at a time (taxicab geometry). We now wonder, how many ways are there, to go from (x1,y1) to (x2,y2) using least steps, and without crossing or touching the line y=x?
Difficulty: Medium.
Input
- Four integers, representing x1, y1, x2, y2, respectively.
Output
The number of ways modulo 10^9+7 to go from (x1,y1) to (x2,y2) using least steps, and without crossing or touching the line y=x.
Example
Given x1=0, y1=-1 which corresponds to the point (0,-1) and x2=1, y2=0 which corresponds to (1,0) there are two ways using least steps: (0,-1)→(0,0)→(1,0) and (0,-1)→(1,-1)→(1,0). But (0,-1)→(0, 0)→(1, 0) touches (0,0) which is on the line y=x and therefore is invalid. Thus, the correct output should be 1.
Solution: C++
#include <iostream>
#include <algorithm>
using namespace::std;
int mod=1000000007;
int const max_x=500; //max value for x1 and x2
int const max_y=500; //max value for y1 and y2
int m[max_x*2][max_y*2]={}; //memorization matrix supposing |x1|,|x2|,|y1|,|y2| <= 500
int lattice_paths(int x1, int y1, int x2, int y2, int dist){
int new_dist=abs(x1-x2)+abs(y1-y2); //euclidean distance from current point to destination
if(new_dist>dist) //not shortest path
return 0;
if(x1==y1) //touched the x=y line
return 0;
if(x1==x2 && y1==y2) //reached destination
return 1;
if(m[x1+max_x][y1+max_y]!=-1) //use memorization of previous calculated paths
return m[x1+max_y][y1+max_y];
// explore all paths
int n=0;
// (a+b)mod p = (a mod p + b mod p)mod p
n=(n%mod+lattice_paths(x1+1,y1,x2,y2,dist-1)%mod)%mod;
n=(n%mod+lattice_paths(x1-1,y1,x2,y2,dist-1)%mod)%mod;
n=(n%mod+lattice_paths(x1,y1+1,x2,y2,dist-1)%mod)%mod;
n=(n%mod+lattice_paths(x1,y1-1,x2,y2,dist-1)%mod)%mod;
if(m[x1+max_x][y1+max_x]==-1) //memorize best solution from current point
m[x1+max_y][y1+max_y]=n;
return n;
}
int main(){
int x1;
int y1;
int x2;
int y2;
cin>>x1;
cin>>y1;
cin>>x2;
cin>>y2;
std::fill(*m, *m + (max_x*2)*(max_y*2), -1); //initialize memorization matrix with -1 as default value
int min_dist=abs(x1-x2)+abs(y1-y2); //calculate initial euclidean distance to destination
int n = lattice_paths(x1,y1,x2,y2,min_dist);
cout<<n;
}
KejiTech 