package main

func walkableTiles(s Ship) map[[2]int]bool {
	walk := make(map[[2]int]bool)
	for _, r := range s.Rooms {
		for y := r.GridY; y < r.GridY+r.GridH; y++ {
			for x := r.GridX; x < r.GridX+r.GridW; x++ {
				walk[[2]int{x, y}] = true
			}
		}
	}
	return walk
}

func bfsPath(walk map[[2]int]bool, from, to [2]int) [][2]int {
	if from == to {
		return nil
	}
	if !walk[to] {
		return nil
	}

	neighbours := [4][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
	visited := map[[2]int]bool{from: true}
	parent := map[[2]int][2]int{}
	queue := [][2]int{from}

	for len(queue) > 0 {
		cur := queue[0]
		queue = queue[1:]
		for _, d := range neighbours {
			next := [2]int{cur[0] + d[0], cur[1] + d[1]}
			if !walk[next] || visited[next] {
				continue
			}
			visited[next] = true
			parent[next] = cur
			if next == to {
				return reconstructPath(parent, from, to)
			}
			queue = append(queue, next)
		}
	}
	return nil
}

func reconstructPath(parent map[[2]int][2]int, from, to [2]int) [][2]int {
	var path [][2]int
	cur := to
	for cur != from {
		path = append(path, cur)
		cur = parent[cur]
	}
	// reverse
	for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 {
		path[i], path[j] = path[j], path[i]
	}
	return path
}