#include <stdlib.h>
static int m, n;
static int **mat;
static int *dp; // dp[i * n + j], 0 = not computed
static const int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
static int max(int a, int b) { return a > b ? a : b; }
static int dfs(int i, int j) {
if (dp[i * n + j] != 0)
return dp[i * n + j]; // already computed
int best = 1; // the cell alone
for (int d = 0; d < 4; d++) {
int ni = i + dirs[d][0], nj = j + dirs[d][1];
if (ni >= 0 && ni < m && nj >= 0 && nj < n && mat[ni][nj] > mat[i][j]) {
best = max(best, 1 + dfs(ni, nj));
}
}
return dp[i * n + j] = best;
}
int longestIncreasingPath(int **matrix, int matrixSize, int *matrixColSize) {
m = matrixSize;
n = matrixColSize[0];
mat = matrix;
dp = calloc(m * n, sizeof(int));
int res = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
res = max(res, dfs(i, j));
free(dp);
return res;
}
#include <algorithm>
#include <vector>
using namespace std;
class Solution {
public:
int m, n;
int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int dfs(int i, int j, vector<vector<int>> &matrix, vector<vector<int>> &dp) {
if (dp[i][j] != 0)
return dp[i][j]; // already computed
int best = 1; // the cell alone
for (auto &d : dirs) {
int ni = i + d[0], nj = j + d[1];
if (ni >= 0 && ni < m && nj >= 0 && nj < n &&
matrix[ni][nj] > matrix[i][j]) {
best = max(best, 1 + dfs(ni, nj, matrix, dp));
}
}
return dp[i][j] = best;
}
int longestIncreasingPath(vector<vector<int>> &matrix) {
m = matrix.size();
n = matrix[0].size();
vector<vector<int>> dp(m, vector<int>(n, 0));
int res = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
res = max(res, dfs(i, j, matrix, dp));
return res;
}
};
package dp
func longestIncreasingPath(matrix [][]int) int {
m, n := len(matrix), len(matrix[0])
dirs := [4][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
dp := make([][]int, m) // 0 = not computed
for i := range dp {
dp[i] = make([]int, n)
}
var dfs func(i, j int) int
dfs = func(i, j int) int {
if dp[i][j] != 0 {
return dp[i][j] // already computed
}
best := 1 // the cell alone
for _, d := range dirs {
ni, nj := i+d[0], j+d[1]
if ni >= 0 && ni < m && nj >= 0 && nj < n && matrix[ni][nj] > matrix[i][j] {
best = max(best, 1+dfs(ni, nj))
}
}
dp[i][j] = best
return best
}
res := 0
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
res = max(res, dfs(i, j))
}
}
return res
}
class Solution {
private int m, n;
private static final int[][] DIRS = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
private int dfs(int i, int j, int[][] matrix, int[][] dp) {
if (dp[i][j] != 0)
return dp[i][j]; // already computed
int best = 1; // the cell alone
for (int[] d : DIRS) {
int ni = i + d[0], nj = j + d[1];
if (ni >= 0 && ni < m && nj >= 0 && nj < n && matrix[ni][nj] > matrix[i][j]) {
best = Math.max(best, 1 + dfs(ni, nj, matrix, dp));
}
}
return dp[i][j] = best;
}
public int longestIncreasingPath(int[][] matrix) {
m = matrix.length;
n = matrix[0].length;
int[][] dp = new int[m][n];
int res = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
res = Math.max(res, dfs(i, j, matrix, dp));
return res;
}
}
/**
* @param {number[][]} matrix
* @return {number}
*/
var longestIncreasingPath = function (matrix) {
const m = matrix.length, n = matrix[0].length;
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const dp = Array.from({ length: m }, () => new Array(n).fill(0)); // 0 = not computed
const dfs = (i, j) => {
if (dp[i][j] !== 0) return dp[i][j]; // already computed
let best = 1; // the cell alone
for (const [di, dj] of dirs) {
const ni = i + di, nj = j + dj;
if (ni >= 0 && ni < m && nj >= 0 && nj < n && matrix[ni][nj] > matrix[i][j]) {
best = Math.max(best, 1 + dfs(ni, nj));
}
}
return (dp[i][j] = best);
};
let res = 0;
for (let i = 0; i < m; i++)
for (let j = 0; j < n; j++) res = Math.max(res, dfs(i, j));
return res;
};
import sys
from typing import List
class Solution:
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
m, n = len(matrix), len(matrix[0])
sys.setrecursionlimit(max(1000, m * n + 100)) # a path can visit every cell
dp = [[0] * n for _ in range(m)] # 0 = not computed
def dfs(i: int, j: int) -> int:
if dp[i][j] != 0:
return dp[i][j] # already computed
best = 1 # the cell alone
for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
ni, nj = i + di, j + dj
if 0 <= ni < m and 0 <= nj < n and matrix[ni][nj] > matrix[i][j]:
best = max(best, 1 + dfs(ni, nj))
dp[i][j] = best
return best
return max(dfs(i, j) for i in range(m) for j in range(n))
impl Solution {
pub fn longest_increasing_path(matrix: Vec<Vec<i32>>) -> i32 {
let (m, n) = (matrix.len(), matrix[0].len());
let mut dp = vec![vec![0; n]; m]; // 0 = not computed
let mut res = 0;
for i in 0..m {
for j in 0..n {
res = res.max(Self::dfs(i, j, &matrix, &mut dp));
}
}
res
}
fn dfs(i: usize, j: usize, matrix: &[Vec<i32>], dp: &mut Vec<Vec<i32>>) -> i32 {
if dp[i][j] != 0 {
return dp[i][j]; // already computed
}
let (m, n) = (matrix.len() as i32, matrix[0].len() as i32);
let mut best = 1; // the cell alone
for (di, dj) in [(1, 0), (-1, 0), (0, 1), (0, -1)] {
let (ni, nj) = (i as i32 + di, j as i32 + dj);
if ni >= 0 && ni < m && nj >= 0 && nj < n {
let (ni, nj) = (ni as usize, nj as usize);
if matrix[ni][nj] > matrix[i][j] {
best = best.max(1 + Self::dfs(ni, nj, matrix, dp));
}
}
}
dp[i][j] = best;
best
}
}