try-snake-ladder-in-golang.go

package main

import (
	"fmt"
)

// NewQueue returns a new queue with the given initial size.
func NewQueue(size int) *Queue {
	return &Queue{
		nodes: make([]*Node, size),
		size:  size,
	}
}

// Queue is a basic FIFO queue based on a circular list that resizes as needed.
type Queue struct {
	nodes []*Node
	size  int
	head  int
	tail  int
	count int
}

// Push adds a node to the queue.
func (q *Queue) Push(n *Node) {
	if q.head == q.tail && q.count > 0 {
		nodes := make([]*Node, len(q.nodes)+q.size)
		copy(nodes, q.nodes[q.head:])
		copy(nodes[len(q.nodes)-q.head:], q.nodes[:q.head])
		q.head = 0
		q.tail = len(q.nodes)
		q.nodes = nodes
	}
	q.nodes[q.tail] = n
	q.tail = (q.tail + 1) % len(q.nodes)
	q.count++
}

// Pop removes and returns a node from the queue in first to last order.
func (q *Queue) Pop() *Node {
	if q.count == 0 {
		return nil
	}
	node := q.nodes[q.head]
	q.head = (q.head + 1) % len(q.nodes)
	q.count--
	return node
}

type Node struct {
	dist int
	v    int
}

func constrArrBool(total int) []bool {
	visited := make([]bool, total+1)
	for i := range visited {
		visited[i] = false
	}

	return visited
}

func constrRouter(a [][]int) map[int]int {
	t := make(map[int]int)
	n := len(a[0])
	direction := 1
	count := 1
	for i := n - 1; i >= 0; i-- {
		if direction == 1 {
			for j := 0; j <= n-1; j++ {
				t[count] = a[i][j]
				count++
			}
			direction = -1
		} else {
			for j := n - 1; j >= 0; j-- {
				t[count] = a[i][j]
				count++
			}
			direction = 1
		}
	}
	return t
}

func snakesAndLadders(board [][]int) int {
	n := len(board[0])
	moves := constrRouter(board)
	total := n * n
	visited := constrArrBool(total)
	visited[1] = true
	queue := NewQueue(total)
	qe := &Node{0, 0}
	queue.Push(qe)

	for queue.size != 0 {
		qe = queue.Pop()
		if qe == nil {
			return -1
		}
		v := qe.v

		if v == total {
			break
		}

		j := v + 1
		for j <= v+6 && j <= total {
			if visited[j] == false {
				visited[j] = true
				move := 0
				if moves[j] != -1 {
					move = moves[j]
				} else {
					move = j
				}
				newA := &Node{qe.dist + 1, move}
				queue.Push(newA)

			}
			j++
		}
	}
	return qe.dist
}

func main() {
	a := [][]int{{-1, -1, -1, -1, -1, -1}, {-1, -1, -1, -1, -1, -1}, {-1, -1, -1, -1, -1, -1}, {-1, 35, -1, -1, 13, -1}, {-1, -1, -1, -1, -1, -1}, {-1, 15, -1, -1, -1, -1}}
	// a := [][]int{{1, 1, -1}, {1, 1, 1}, {-1, 1, 1}}
	// a := [][]int{{-1, 1, 2, -1}, {2, 13, 15, -1}, {-1, 10, -1, -1}, {-1, 6, 2, 8}}
	res := snakesAndLadders(a)
	fmt.Println("res:", res)
}