動的計画法で低いマスから順に埋め、グリッドの上り続ける最長の道を求める

STEPS = ((1, 0), (-1, 0),
         (0, 1), (0, -1))


def lower(g, r, c):
    for dr, dc in STEPS:
        y, x = r + dr, c + dc
        if y < 0 or x < 0:
            continue
        if y >= len(g):
            continue
        if x >= len(g[0]):
            continue
        if g[y][x] < g[r][c]:
            yield y, x


def longest_rise(heights):
    g = heights
    rows = range(len(g))
    cols = range(len(g[0]))
    cells = sorted(
        (g[r][c], r, c)
        for r in rows
        for c in cols
    )
    best = [[1] * len(cols)
            for _ in rows]
    answer = 0
    for _, r, c in cells:
        low = lower(g, r, c)
        for y, x in low:
            n = best[y][x] + 1
            if n > best[r][c]:
                best[r][c] = n
        if best[r][c] > answer:
            answer = best[r][c]
    return answer

const STEPS = [
  [1, 0], [-1, 0],
  [0, 1], [0, -1],
];

function lower(g, r, c) {
  const out = [];
  for (const d of STEPS) {
    const y = r + d[0];
    const x = c + d[1];
    const row = g[y];
    if (row === undefined) {
      continue;
    }
    if (row[x] < g[r][c]) {
      out.push([y, x]);
    }
  }
  return out;
}

function longestRise(heights) {
  const g = heights;
  const cells = [];
  g.forEach((row, r) => {
    row.forEach((h, c) => {
      cells.push([h, r, c]);
    });
  });
  cells.sort(
    (p, q) => p[0] - q[0],
  );
  const best = g.map(
    (row) => row.map(() => 1),
  );
  let answer = 0;
  for (const cell of cells) {
    const [, r, c] = cell;
    const low = lower(g, r, c);
    for (const [y, x] of low) {
      const n = best[y][x] + 1;
      if (n > best[r][c]) {
        best[r][c] = n;
      }
    }
    if (best[r][c] > answer) {
      answer = best[r][c];
    }
  }
  return answer;
}

import "sort"

var steps = [][2]int{
	{1, 0}, {-1, 0},
	{0, 1}, {0, -1},
}

func lower(
	g [][]int, r, c int,
) [][2]int {
	out := [][2]int{}
	for _, s := range steps {
		y, x := r+s[0], c+s[1]
		if y < 0 || y >= len(g) {
			continue
		}
		if x < 0 || x >= len(g[y]) {
			continue
		}
		if g[y][x] < g[r][c] {
			p := [2]int{y, x}
			out = append(out, p)
		}
	}
	return out
}

func longestRise(
	heights [][]int,
) int {
	g := heights
	cells := [][2]int{}
	best := make([][]int, len(g))
	for r := range g {
		n := len(g[r])
		best[r] = make([]int, n)
		for c := range g[r] {
			p := [2]int{r, c}
			cells = append(cells, p)
			best[r][c] = 1
		}
	}
	high := func(i int) int {
		p := cells[i]
		return g[p[0]][p[1]]
	}
	less := func(i, j int) bool {
		return high(i) < high(j)
	}
	sort.Slice(cells, less)
	answer := 0
	for _, p := range cells {
		r, c := p[0], p[1]
		low := lower(g, r, c)
		for _, q := range low {
			n := best[q[0]][q[1]] + 1
			if n > best[r][c] {
				best[r][c] = n
			}
		}
		if best[r][c] > answer {
			answer = best[r][c]
		}
	}
	return answer
}