Sponsored
Sponsored
This approach uses Depth First Search (DFS) combined with memoization to count the number of increasing paths starting from each cell. The main idea is to recursively explore each cell's neighbors, moving to the next cell only if its value is higher, and storing intermediate results to avoid redundant calculations.
Time Complexity: O(m*n), where m and n are the dimensions of the grid. Each cell is visited once.
Space Complexity: O(m*n) due to the memoization table.
1MOD = 10**9 + 7
2
3def count_paths(grid):
4 m, n = len(grid), len(grid[0])
5 directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
6 dp = [[-1]*n for _ in range(m)]
7
8 def dfs(x, y):
9 if dp[x][y] != -1:
10 return dp[x][y]
11 path_count = 1 # count the path of length 1 (itself)
12 for dx, dy in directions:
13 nx, ny = x + dx, y + dy
14 if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] > grid[x][y]:
15 path_count = (path_count + dfs(nx, ny)) % MOD
16 dp[x][y] = path_count
17 return dp[x][y]
18
19 total_paths = 0
20 for i in range(m):
21 for j in range(n):
22 total_paths = (total_paths + dfs(i, j)) % MOD
23 return total_paths
24
25# Example Usage
26grid = [[1, 1], [3, 4]]
27print(count_paths(grid)) # Output: 8
28The Python solution implements DFS with memoization to explore each cell's increasing paths. A 2D list 'dp' stores the number of paths starting from each cell and is initialized to -1. The function 'dfs' calculates paths from the starting cell using recursion and updating the 'dp' table to avoid redundant calculations. Results are computed modulo 10^9 + 7 to handle large path counts.
This approach involves sorting the cells of the grid based on their values and then using dynamic programming to calculate the number of increasing paths from each cell. By processing cells in increasing order, we ensure that when calculating the number of paths for a cell, all smaller cells have been processed.
Time Complexity: O(m*n*log(m*n)), primarily due to sorting m*n cells.
Space Complexity: O(m*n) for the paths storage.
1#include <vector>
2#include <algorithm>
3using namespace std;
4const int MOD = 1e9 + 7;
5
int countPaths(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> paths(m, vector<int>(n, 1));
vector<pair<int, int>> cells;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
cells.emplace_back(i, j);
}
}
sort(cells.begin(), cells.end(), [&](pair<int, int> a, pair<int, int> b) {
return grid[a.first][a.second] < grid[b.first][b.second];
});
int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
for (auto [x, y] : cells) {
for (auto [dx, dy] : directions) {
int nx = x + dx, ny = y + dy;
if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] > grid[x][y]) {
paths[nx][ny] = (paths[nx][ny] + paths[x][y]) % MOD;
}
}
}
int total_paths = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
total_paths = (total_paths + paths[i][j]) % MOD;
}
}
return total_paths;
}
// Example Usage
// vector<vector<int>> grid = {{1, 1}, {3, 4}};
// cout << countPaths(grid) << endl; // Output: 8
The C++ solution performs topological sorting based on grid values. It initially sets up each cell with a path count of 1. Cells are processed in value order using a vector of pairs, sorted by their value. For each cell, we explore adjacent cells that contain larger values, updating path counts as we go, ensuring earlier cells' paths are calculated before later ones, thus respecting dependencies.