2912. Number of Ways to Reach Destination in the Grid

You are given two integers n and m which represent the size of a 1-indexed grid. You are also given an integer k, a 1-indexed integer array source and a 1-indexed integer array dest, where source and dest are in the form [x, y] representing a cell on the given grid.

You can move through the grid in the following way:

• You can go from cell [x1, y1] to cell [x2, y2] if either x1 == x2 or y1 == y2.
• Note that you can’t move to the cell you are already in e.g. x1 == x2 and y1 == y2.

Return the number of ways you can reach dest from source by moving through the grid exactly k times.

Since the answer may be very large, return it modulo 109 + 7.

class Solution {
public:
    int numberOfWays(int n, int m, int k, vector<int>& source, vector<int>& dest) {
        long long mod = 1e9 + 7, cent = 1, r = 0, c = 0, o = 0;
        while(k--) {
            long long pcent = cent, pr = r, pc = c, po = o;
            cent = (pr * (m - 1) + pc * (n - 1)) % mod;
            r = (pr * (m - 2) + pcent + po * (n - 1)) % mod;
            c = (pc * (n - 2) + pcent + po * (m - 1)) % mod;
            o = (po * (m - 2) + po * (n - 2) + pc + pr) % mod;
        }
        if(source == dest) return cent;
        if(source[0] == dest[0]) return r;
        if(source[1] == dest[1]) return c;
        return o;
    }
};