LeetCode/576.cpp at master · chinawch007/LeetCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/*
    不是以对格子的迭代为主体,而是以步数的迭代为主体

*/

#include<vector>
#include<string>
#include<map>

using namespace std;

class Solution {
public:
    int findPaths(int m, int n, int N, int i, int j) {

        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                dp[i][j][1] = 0;
            }
        }

        for(int i = 0; i < m; ++i)
        {
            dp[i][0][1] += 1;
            dp[i][n-1][1] += 1;
        }

        for(int j = 0; j < n; ++j)
        {
            dp[0][j][1] += 1;
            dp[m-1][j][1] += 1;
        }

        for(int k = 2; k <= N; ++k)
        {
            for(int i = 0; i < m; ++i)
            {
                for(int j = 0; j < n; ++j)
                {
                    dp[i][j][k] = 0;
                    if(i-1 >= 0)dp[i][j][k] = (int)(((long)dp[i][j][k] +(long) dp[i-1][j][k-1]) % 1000000007);
                    if(i+1 < m)dp[i][j][k] = (int)(((long)dp[i][j][k] + (long)dp[i+1][j][k-1]) % 1000000007);
                    if(j-1 >= 0)dp[i][j][k] = (int)(((long)dp[i][j][k] + (long)dp[i][j-1][k-1]) % 1000000007);
                    if(j+1 < n)dp[i][j][k] = (int)(((long)dp[i][j][k] + (long)dp[i][j+1][k-1]) % 1000000007);
                }
            }
        }

        long ret = 0;
        for(int k = 1; k <= N; ++k)
        {
            ret += dp[i][j][k];
            ret %= 1000000007;
        }


        return (int)ret;
    }

    int dp[50][50][51];
};