Skip to content

3459. Length of Longest V-Shaped Diagonal Segment

  • Time: $O(4mn \cdot \max(m, n)) = O(mn \cdot \max(m, n))$
  • Space: $O(mn \cdot 2^2 \cdot 4) = O(mn)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
 public:
  int lenOfVDiagonal(vector<vector<int>>& grid) {
    const int m = grid.size();
    const int n = grid[0].size();
    vector<vector<vector<vector<vector<int>>>>> mem(
        m, vector<vector<vector<vector<int>>>>(
               n, vector<vector<vector<int>>>(
                      2, vector<vector<int>>(2, vector<int>(4, -1)))));
    int res = 0;

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        if (grid[i][j] == 1)
          for (int d = 0; d < 4; ++d) {
            const auto& [dx, dy] = kDirs[d];
            res = max(res, 1 + dfs(grid, i + dx, j + dy, /*turned=*/false, 2, d,
                                   mem));
          }

    return res;
  }

 private:
  static constexpr int kDirs[4][2] = {{-1, 1}, {1, 1}, {1, -1}, {-1, -1}};

  int dfs(const vector<vector<int>>& grid, int i, int j, bool turned, int num,
          int dir, vector<vector<vector<vector<vector<int>>>>>& mem) {
    if (i < 0 || i == grid.size() || j < 0 || j == grid[0].size())
      return 0;
    if (grid[i][j] != num)
      return 0;

    const int hashNum = max(0, num - 1);
    if (mem[i][j][turned][hashNum][dir] != -1)
      return mem[i][j][turned][hashNum][dir];

    const int nextNum = num == 2 ? 0 : 2;
    const auto& [dx, dy] = kDirs[dir];
    int res = 1 + dfs(grid, i + dx, j + dy, turned, nextNum, dir, mem);

    if (!turned) {
      const int nextDir = (dir + 1) % 4;
      const auto& [nextDx, nextDy] = kDirs[nextDir];
      res = max(res, 1 + dfs(grid, i + nextDx, j + nextDy, /*turned=*/true,
                             nextNum, nextDir, mem));
    }

    return mem[i][j][turned][hashNum][dir] = res;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
  public int lenOfVDiagonal(int[][] grid) {
    final int m = grid.length;
    final int n = grid[0].length;
    Integer[][][][][] mem = new Integer[m][n][2][2][4];

    int ans = 0;

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        if (grid[i][j] == 1)
          for (int d = 0; d < 4; ++d) {
            final int dx = DIRS[d][0];
            final int dy = DIRS[d][1];
            ans = Math.max(ans, 1 + dfs(grid, i + dx, j + dy, /*turned=*/false, 2, d, mem));
          }

    return ans;
  }

  private static final int[][] DIRS = {{-1, 1}, {1, 1}, {1, -1}, {-1, -1}};

  private int dfs(int[][] grid, int i, int j, boolean turned, int num, int dir,
                  Integer[][][][][] mem) {
    if (i < 0 || i == grid.length || j < 0 || j == grid[0].length)
      return 0;
    if (grid[i][j] != num)
      return 0;

    final int hashNum = Math.max(0, num - 1);
    if (mem[i][j][turned ? 1 : 0][hashNum][dir] != null)
      return mem[i][j][turned ? 1 : 0][hashNum][dir];

    final int nextNum = num == 2 ? 0 : 2;
    final int dx = DIRS[dir][0], dy = DIRS[dir][1];
    int res = 1 + dfs(grid, i + dx, j + dy, turned, nextNum, dir, mem);

    if (!turned) {
      final int nextDir = (dir + 1) % 4;
      final int nextDx = DIRS[nextDir][0], nextDy = DIRS[nextDir][1];
      res = Math.max(res,
                     1 + dfs(grid, i + nextDx, j + nextDy, /*turned=*/true, nextNum, nextDir, mem));
    }

    return mem[i][j][turned ? 1 : 0][hashNum][dir] = res;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
  def lenOfVDiagonal(self, grid: list[list[int]]) -> int:
    DIRS = ((-1, 1), (1, 1), (1, -1), (-1, -1))

    @functools.lru_cache(None)
    def dfs(i: int, j: int, turned: bool, num: int, dir: int) -> int:
      if i < 0 or i == len(grid) or j < 0 or j == len(grid[0]):
        return 0
      if grid[i][j] != num:
        return 0

      nextNum = 0 if num == 2 else 2
      dx, dy = DIRS[dir]
      res = 1 + dfs(i + dx, j + dy, turned, nextNum, dir)

      if not turned:
        nextDir = (dir + 1) % 4
        nextDx, nextDy = DIRS[nextDir]
        res = max(res, 1 + dfs(i + nextDx, j + nextDy, 1, nextNum, nextDir))

      return res

    return max((1 + dfs(i + dx, j + dy, 0, 2, d)
                for i, row in enumerate(grid)
                for j, num in enumerate(row)
                if num == 1
                for d, (dx, dy) in enumerate(DIRS)),
               default=0)