LeetCode/go/minimum-cost-to-make-at-least-one-valid-path-in-a-grid.go

package main

import aq "github.com/emirpasic/gods/v2/queues/arrayqueue"

type Coord struct {
	y int
	x int
}

func (c *Coord) Add(rhs Coord) Coord {
	return Coord{
		y: c.y + rhs.y,
		x: c.x + rhs.x,
	}
}

func minCost(grid [][]int) int {
	UNVISITED := 10000001
	DIRS := []Coord{
		Coord{0, 1},
		Coord{0, -1},
		Coord{1, 0},
		Coord{-1, 0},
	}

	width, height := len(grid[0]), len(grid)
	inBounds := func(pos Coord) bool {
		return pos.y >= 0 && pos.y < height && pos.x >= 0 && pos.x < width
	}

	dp := make([][]int, height)
	for i, _ := range dp {
		dp[i] = make([]int, width)
		for j, _ := range dp[i] {
			dp[i][j] = UNVISITED
		}
	}
	isVisited := func(pos Coord) bool {
		return dp[pos.y][pos.x] != UNVISITED
	}

	q := aq.New[Coord]()

	var dfs func(int, Coord)
	dfs = func(cost int, pos Coord) {
		if !inBounds(pos) || isVisited(pos) {
			return
		}

		dp[pos.y][pos.x] = cost
		q.Enqueue(pos)

		// follow the direction
		dirIdx := grid[pos.y][pos.x] - 1
		dfs(cost, pos.Add(DIRS[dirIdx]))
	}

	cost := 0
	dfs(cost, Coord{0, 0})

	for !q.Empty() {
		cost++

		size := q.Size()
		for i := 0; i < size; i++ {
			pos, _ := q.Dequeue()

			for _, dir := range DIRS {
				dfs(cost, pos.Add(dir))
			}
		}
	}

	return dp[height-1][width-1]
}