Problem: 3459. 最长 V 形对角线段的长度

思路

深度优先搜索 + 记忆数组

解题过程

主函数和先遍历从每一个1开始搜索，并枚举每一个方向进入dfs，dfs先检查是否遍历过，然后枚举下一个可以走的方向，最后返回最值即可。

复杂度

• 时间复杂度: $O(n^2)$
• 空间复杂度: $O(n^2)$

Code

class Solution {
public:int maxlen = 0;array<int, 4> dx{1, 1, -1, -1};array<int, 4> dy{1, -1, -1,  1};int m, n;vector<vector<int>> grid;int memo[505][505][3][2][4];int dfs(int px, int py, int pn, int changed, int drec) {if (memo[px][py][pn][changed][drec] != -1) return memo[px][py][pn][changed][drec];int need = (pn == 2 ? 0 : 2);int best = 1;int nx = px + dx[drec], ny = py + dy[drec];if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == need) {best = max(best, 1 + dfs(nx, ny, need, changed, drec));}if (!changed) {int nd = (drec + 1) % 4;int tx = px + dx[nd], ty = py + dy[nd];if (tx >= 0 && tx < n && ty >= 0 && ty < m && grid[tx][ty] == need) {best = max(best, 1 + dfs(tx, ty, need, 1, nd));}}memo[px][py][pn][changed][drec] = best;if (best > maxlen) maxlen = best;return best;}int lenOfVDiagonal(vector<vector<int>>& ggrid) {grid = ggrid;n = grid.size();m = grid[0].size();maxlen = 0;memset(memo, -1, sizeof(memo));for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if (grid[i][j] == 1) {for (int k = 0; k < 4; ++k) {dfs(i, j, 1, 0, k);}}}}return maxlen;}
};