Lattice Paths

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;
}

Related posts

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s