(direction + 1) % 4). For this new path, can_turn will be set to false.

The result for the current state is 1 + max(path_straight, path_turned). This is stored in our memoization table.

Final Result: The answer is the maximum length found across all possible starting points and directions.

Code

[{"language":"C++","code":"#include <vector>\n#include <map>\n#include <tuple>\n#include <algorithm>\n\nusing namespace std;\n\nclass Solution {\npublic:\n    int m, n;\n    vector<vector<int>> grid;\n    vector<pair<int, int>> dirs = {{1, 1}, {1, -1}, {-1, -1}, {-1, 1}};\n    map<tuple<int, int, int, bool>, int> memo;\n\n    int dfs(int cx, int cy, int direction, bool can_turn, int target) {\n        int nx = cx + dirs[direction].first;\n        int ny = cy + dirs[direction].second;\n\n        if (nx < 0 || ny < 0 || nx >= m || ny >= n || grid[nx][ny] != target) {\n            return 0;\n        }\n\n        auto key = make_tuple(nx, ny, direction, can_turn);\n        if (memo.count(key)) {\n            return memo[key];\n        }\n\n        int max_step = dfs(nx, ny, direction, can_turn, 2 - target);\n        if (can_turn) {\n            max_step = max(max_step, dfs(nx, ny, (direction + 1) % 4, false, 2 - target));\n        }\n        \n        return memo[key] = max_step + 1;\n    }\n\n    int lenOfVDiagonal(vector<vector<int>>& grid) {\n        this->grid = grid;\n        this->m = grid.size();\n        this->n = grid[0].size();\n        \n        int res = 0;\n        for (int i = 0; i < m; i++) {\n            for (int j = 0; j < n; j++) {\n                if (grid[i][j] == 1) {\n                    for (int direction = 0; direction < 4; direction++) {\n                        res = max(res, dfs(i, j, direction, true, 2) + 1);\n                    }\n                }\n            }\n        }\n        return res;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">#include</span><span style=\"color:#032F62;--shiki-dark:#9ECBFF\"> &#x3C;vector></span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">#include</span><span style=\"color:#032F62;--shiki-dark:#9ECBFF\"> &#x3C;map></span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">#include</span><span style=\"color:#032F62;--shiki-dark:#9ECBFF\"> &#x3C;tuple></span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">#include</span><span style=\"color:#032F62;--shiki-dark:#9ECBFF\"> &#x3C;algorithm></span></span>\n<span class=\"line\"></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">using</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">

Related Tags