C++ code, beat 100% of C++ submissions!


  • 0
    D

    C++ Code
    Time Complexity: O(Nmn)
    Space Complexity: O(m*n)
    Beat 100% of C++ Submissions!

    int findPaths(int m, int n, int N, int i, int j) {
            vector<vector<int>> T1 = vector<vector<int>>(m, vector<int>(n, 0)), T2 = T1;
            for (unsigned int k = 0; k < N; k++) {
                for (unsigned int row = 0; row < m; row++) {
                    for (unsigned int col = 0; col < n; col++) {
                        T2[row][col] += row == 0 ? 1 : T1[row - 1][col] % (unsigned int)(pow(10.0, 9) + 7);
                        T2[row][col] += col == 0 ? 1 : T1[row][col - 1] % (unsigned int)(pow(10.0, 9) + 7);
                        T2[row][col] += row == m - 1 ? 1 : T1[row + 1][col] % (unsigned int)(pow(10.0, 9) + 7);
                        T2[row][col] += col == n - 1 ? 1 : T1[row][col + 1] % (unsigned int)(pow(10.0, 9) + 7);
                    }
                }
                T1 = T2;
                T2 = vector<vector<int>>(m, vector<int>(n, 0));
            }
            return T1[i][j] % (unsigned int)(pow(10.0, 9) + 7);
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.