package main

import (
	"cmp"

	pq "github.com/emirpasic/gods/v2/queues/priorityqueue"
)

type Position struct {
	y, x int
}

func (p *Position) add(v Position) Position {
	return Position{
		y: p.y + v.y,
		x: p.x + v.x,
	}
}

type QueueEntry struct {
	time int
	pos  Position
}

func byTime(a, b QueueEntry) int {
	return cmp.Compare(a.time, b.time)
}

func minimumTime(grid [][]int) int {
	if grid[0][1] > 1 && grid[1][0] > 1 {
		return -1
	}
	DIRECTIONS := []Position{
		Position{1, 0}, Position{-1, 0}, Position{0, 1}, Position{0, -1},
	}

	rows, cols := len(grid), len(grid[0])
	visited := make([][]bool, rows)
	for i, _ := range visited {
		visited[i] = make([]bool, cols)
	}

	valid := func(pos Position) bool {
		return pos.y >= 0 && pos.y < len(visited) &&
			pos.x >= 0 && pos.x < len(visited[pos.y]) &&
			!visited[pos.y][pos.x]
	}

	q := pq.NewWith[QueueEntry](byTime)
	q.Enqueue(QueueEntry{grid[0][0], Position{0, 0}})

	for current, ok := q.Dequeue(); ok; current, ok = q.Dequeue() {
		if current.pos.y == rows-1 && current.pos.x == cols-1 {
			return current.time
		}

		if visited[current.pos.y][current.pos.x] {
			continue
		}
		visited[current.pos.y][current.pos.x] = true

		for _, dir := range DIRECTIONS {
			next := current.pos.add(dir)
			if !valid(next) {
				continue
			}

			waiting := 0
			if (grid[next.y][next.x]-current.time)%2 == 0 {
				waiting = 1
			}

			q.Enqueue(QueueEntry{pos: next, time: max(grid[next.y][next.x]+waiting, current.time+1)})
		}
	}

	return -1
}