675.md

674. Longest Continuous Increasing Subsequence

Solution 1 (time O(m^2*n^2), space O(1))

class Solution(object):
    def cutOffTree(self, forest):
        """
        :type forest: List[List[int]]
        :rtype: int
        """
        def bfs(sx, sy, tx, ty):
            m, n = len(forest), len(forest[0])
            q = deque([(0, sx, sy)])
            vis = set([(sx, sy)])
            while q:
                d, cur_x, cur_y = q.popleft()
                if cur_x == tx and cur_y == ty:
                    return d
                for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                    new_x = cur_x + dx
                    new_y = cur_y + dy
                    if 0 <= new_x < m and 0 <= new_y < n and forest[new_x][new_y] and (new_x, new_y) not in vis:
                        vis.add((new_x, new_y))
                        q.append((d + 1, new_x, new_y))
            return -1

        trees = sorted((h, i, j) for i, row in enumerate(forest) for j, h in enumerate(row) if h > 1)
        ans = 0
        sx, sy = 0, 0
        for _, i, j in trees:
            d = bfs(sx, sy, i, j)
            if d < 0:
                return -1
            ans += d
            sx, sy = i, j
        return ans