Problem

There is an m by n grid with a ball. Given the start coordinate (i,j) of the ball, you can move the ball to adjacent cell or cross the grid boundary in four directions (up, down, left, right). However, you can at most move N times. Find out the number of paths to move the ball out of grid boundary. The answer may be very large, return it after mod 10⁹ + 7.

Example 1:

Input:m = 2, n = 2, N = 2, i = 0, j = 0
Output: 6
Explanation:

Example 2:

Input:m = 1, n = 3, N = 3, i = 0, j = 1
Output: 12
Explanation:

Note:

Once you move the ball out of boundary, you cannot move it back.
The length and height of the grid is in range [1,50].
N is in range [0,50].

Solution

Time complexity: O(m*n + N * m * n)

Space complexity: O(N*m*n) -> O(m*n)

C++

// Author: Huahua

// Running time: 19 ms

class Solution {

public:

int findPaths(int m, int n, int N, int i, int j) {

constexpr int kMod = 1000000007;

vector<vector<vector<int>>> dp(N + 1, vector<vector<int>>(m, vector<int>(n, 0)));

vector<int> dirs{-1, 0, 1, 0, -1};

for (int s = 1; s <= N; ++s)

for (int y = 0; y < m; ++y)

for (int x = 0; x < n; ++x)

for (int d = 0; d < 4; ++d) {

int tx = x + dirs[d];

int ty = y + dirs[d + 1];

if (tx < 0 || ty < 0 || tx >= n || ty >= m)

dp[s][y][x] += 1;

else

dp[s][y][x] = (dp[s][y][x] + dp[s - 1][ty][tx]) % kMod;

}

return dp[N][i][j];

}

};

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

int findPaths(int m, int n, int N, int i, int j) {

constexpr int kMod = 1000000007;

vector<vector<int>> dp(m, vector<int>(n, 0));

vector<int> dirs{-1, 0, 1, 0, -1};

for (int s = 1; s <= N; ++s) {

vector<vector<int>> tmp(m, vector<int>(n, 0));

for (int y = 0; y < m; ++y)

for (int x = 0; x < n; ++x)

for (int d = 0; d < 4; ++d) {

int tx = x + dirs[d];

int ty = y + dirs[d + 1];

if (tx < 0 || ty < 0 || tx >= n || ty >= m)

tmp[y][x] += 1;

else

tmp[y][x] = (tmp[y][x] + dp[ty][tx]) % kMod;

}

dp.swap(tmp);

}

return dp[i][j];

}

};

Recursion with memorization

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int findPaths(int m, int n, int N, int i, int j) {

m_ = m;

n_ = n;

dp_ = vector<vector<vector<int>>>(N + 1, vector<vector<int>>(m, vector<int>(n, INT_MIN)));

return paths(N, j, i);

}

private:

vector<vector<vector<int>>> dp_;

int m_;

int n_;

// number of paths starts from out-of-boundary to (x, y) by moving at most N steps.

int paths(int N, int x, int y) {

static vector<int> dirs{-1, 0, 1, 0, -1};

static const int kMod = 1000000007;

// Out of boundary, one path.

if (x < 0 || x >= n_ || y < 0 || y >= m_) return 1;

// Can not move but still in the grid, no path.

if (N == 0) return 0;

// Already computed.

if (dp_[N][y][x] != INT_MIN) return dp_[N][y][x];

dp_[N][y][x] = 0;

for (int d = 0; d < 4; ++d) {

int tx = x + dirs[d];

int ty = y + dirs[d + 1];

dp_[N][y][x] = (dp_[N][y][x] + paths(N - 1, tx, ty)) % kMod;

}

return dp_[N][y][x];

}

};

no loops

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int findPaths(int m, int n, int N, int i, int j) {

m_ = m;

n_ = n;

dp_ = vector<vector<vector<int>>>(N + 1, vector<vector<int>>(m, vector<int>(n, INT_MIN)));

return paths(N, j, i);

}

private:

vector<vector<vector<int>>> dp_;

int m_;

int n_;

// number of paths start from (x, y) and move at most N steps.

int paths(int N, int x, int y) {

static const int kMod = 1000000007;

if (x < 0 || x >= n_ || y < 0 || y >= m_) return 1;

if (N == 0) return 0;

if (dp_[N][y][x] != INT_MIN) return dp_[N][y][x];

long ans = 0;

ans += paths(N - 1, x + 1, y);

ans += paths(N - 1, x - 1, y);

ans += paths(N - 1, x, y + 1);

ans += paths(N - 1, x, y - 1);

ans %= kMod;

return dp_[N][y][x] = ans;

}

};

花花酱 LeetCode 576. Out of Boundary Paths

Problem

Solution

Related Problems

Be First to Comment

Leave a Reply Cancel reply