diff options
author | Jack Sangdahl <[email protected]> | 2025-08-26 21:08:37 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-08-26 21:08:37 -0600 |
commit | f549305fb5ca531d29dce6c2c091560f44190443 (patch) | |
tree | 5d7ddaabb9ad250ef16f1c3fbea9e528643afdf9 | |
parent | 93bbf9764ee8020da1c2914d16bc6c9698e3c329 (diff) | |
download | leetcode-f549305fb5ca531d29dce6c2c091560f44190443.tar.gz leetcode-f549305fb5ca531d29dce6c2c091560f44190443.zip |
3459. length of longest v-shaped diagonal segment
-rw-r--r-- | length_longest_vshape_diag_seg.c | 86 | ||||
-rw-r--r-- | length_longest_vshape_diag_seg.py | 78 |
2 files changed, 164 insertions, 0 deletions
diff --git a/length_longest_vshape_diag_seg.c b/length_longest_vshape_diag_seg.c new file mode 100644 index 0000000..619fa02 --- /dev/null +++ b/length_longest_vshape_diag_seg.c @@ -0,0 +1,86 @@ +// 3459. Length of Longest V-Shaped Diagonal Segment +#include "leetcode.h" + +/* + * you are given a 2d integer matrix 'grid' of size 'n x m', where each element + * is either 0, 1, or 2. a v-shaped diagonal segment is defined as: the segment + * starts with 1, the subsequent elements follow this infinite sequence '2, 0, + * 2, 0, ...', the segment starts along a diagonal direction, the segment + * continues the sequence in the same diagonal direction, and the segment makes + * at most one clockwise 90-degree turn to another diagonal direction while + * maintaining the sequence. + */ + +const static int dx[] = {1, 1, -1, -1}, dy[] = {1, -1, -1, 1}; +int dp[501][501][4][2]; + +bool pos(int **grid, int gridSize, int *gridColSize, int x, int y, int nx, + int ny) { + return nx >= 0 && ny >= 0 && nx < gridSize && ny < gridColSize[0] && + abs(grid[x][y] - grid[nx][ny]) == 2; +} + +int dfs(int **grid, int gridSize, int *gridColSize, int x, int y, int d, + int changed) { + if (dp[x][y][d][changed] != -1) + return dp[x][y][d][changed]; + int res = 1; + if (pos(grid, gridSize, gridColSize, x, y, x + dx[d], y + dy[d])) + res = fmax( + res, + dfs(grid, gridSize, gridColSize, x + dx[d], y + dy[d], d, changed) + 1); + if (!changed) { + int nd = (d + 1) % 4; + if (pos(grid, gridSize, gridColSize, x, y, x + dx[nd], y + dy[nd])) + res = fmax(res, dfs(grid, gridSize, gridColSize, x + dx[nd], y + dy[nd], + nd, changed + 1) + + 1); + } + return dp[x][y][d][changed] = res; +} + +int lenOfVDiagonal(int **grid, int gridSize, int *gridColSize) { + const int n = gridSize, m = gridColSize[0]; + int ans = 0; + memset(dp, -1, sizeof(dp)); + for (int i = 0; i < gridSize; ++i) + for (int j = 0; j < gridColSize[0]; ++j) + if (grid[i][j] == 1) { + ans = fmax(ans, 1); + for (int k = 0; k < 4; ++k) { + int nx = i + dx[k], ny = j + dy[k]; + if (nx < 0 || ny < 0 || nx >= n || ny >= m || grid[nx][ny] != 2) + continue; + ans = fmax(ans, dfs(grid, gridSize, gridColSize, nx, ny, k, 0) + 1); + } + } + return ans; +} + +int main() { + int g1i[5][5] = {{2, 2, 1, 2, 2}, + {2, 0, 2, 2, 0}, + {2, 0, 1, 1, 0}, + {1, 0, 2, 2, 2}, + {2, 0, 0, 2, 2}}; + int g2i[5][5] = {{2, 2, 2, 2, 2}, + {2, 0, 2, 2, 0}, + {2, 0, 1, 1, 0}, + {1, 0, 2, 2, 2}, + {2, 0, 0, 2, 2}}; + int g3i[5][5] = {{1, 2, 2, 2, 2}, + {2, 2, 2, 2, 0}, + {2, 0, 0, 0, 0}, + {0, 0, 2, 2, 2}, + {2, 0, 0, 2, 0}}; + struct two_d_arr g1, g2, g3; + two_d_arr_init(&g1, ARRAY_SIZE(g1i), ARRAY_SIZE(g1i[0]), g1i); + two_d_arr_init(&g2, ARRAY_SIZE(g2i), ARRAY_SIZE(g2i[0]), g2i); + two_d_arr_init(&g3, ARRAY_SIZE(g3i), ARRAY_SIZE(g3i[0]), g3i); + printf("%d\n", lenOfVDiagonal(g1.arr, g1.row_size, g1.col_size)); // expect: 5 + printf("%d\n", lenOfVDiagonal(g2.arr, g2.row_size, g2.col_size)); // expect: 4 + printf("%d\n", lenOfVDiagonal(g3.arr, g3.row_size, g3.col_size)); // expect: 5 + two_d_arr_free(&g1); + two_d_arr_free(&g2); + two_d_arr_free(&g3); +} diff --git a/length_longest_vshape_diag_seg.py b/length_longest_vshape_diag_seg.py new file mode 100644 index 0000000..bd7c875 --- /dev/null +++ b/length_longest_vshape_diag_seg.py @@ -0,0 +1,78 @@ +# 3459. Length of Longest V-Shaped Diagonal Segment + +""" +you are given a 2d integer matrix 'grid' of size 'n x m', where each element +is either 0, 1, or 2. a v-shaped diagonal segment is defined as: the segment +starts with 1, the subsequent elements follow this infinite sequence '2, 0, +2, 0, ...', the segment starts along a diagonal direction, the segment +continues the sequence in the same diagonal direction, and the segment makes +at most one clockwise 90-degree turn to another diagonal direction while +maintaining the sequence. +""" + + +class Solution(object): + def lenOfVDiagonal(self, grid): + """ + :type grid: List[List[int]] + :rtype: int + """ + ds = [[1, 1], [1, -1], [-1, -1], [-1, 1]] + nx = [2, 2, 0] + ans, n, m = 0, len(grid), len(grid[0]) + + def dp(i, j, x, d, k): + if not (0 <= i < n and 0 <= j < m): + return 0 + if grid[i][j] != x: + return 0 + res = dp(i + ds[d][0], j + ds[d][1], nx[x], d, k) + 1 + if k > 0: + d2 = (d + 1) % 4 + res2 = dp(i + ds[d2][0], j + ds[d2][1], nx[x], d2, 0) + 1 + res = max(res, res2) + return res + + for i in range(n): + for j in range(m): + if grid[i][j] == 1: + curr = max(dp(i, j, 1, d, 1) for d in range(4)) + ans = max(ans, curr) + return ans + + +if __name__ == "__main__": + obj = Solution() + print( + obj.lenOfVDiagonal( + grid=[ + [2, 2, 1, 2, 2], + [2, 0, 2, 2, 0], + [2, 0, 1, 1, 0], + [1, 0, 2, 2, 2], + [2, 0, 0, 2, 2], + ] + ) + ) + print( + obj.lenOfVDiagonal( + grid=[ + [2, 2, 2, 2, 2], + [2, 0, 2, 2, 0], + [2, 0, 1, 1, 0], + [1, 0, 2, 2, 2], + [2, 0, 0, 2, 2], + ] + ) + ) + print( + obj.lenOfVDiagonal( + grid=[ + [1, 2, 2, 2, 2], + [2, 2, 2, 2, 0], + [2, 0, 0, 0, 0], + [0, 0, 2, 2, 2], + [2, 0, 0, 2, 0], + ] + ) + ) |