// step 1: 初始化
// 把初始节点放到 queue 里，如果有多个就都放进去
// 并标记初始节点的距离为 0，记录在 distance 的 hashmap 里
// distance 有两个作用，一是判断是否已经访问过，二是记录离起点的距离
queue := []*Node{node}
distance := map[*Node]int64{
	node: 0,
}

// step 2: 不断访问队列
// while 循环 + 每次 pop 队列中的一个点出来
for len(queue) > 0 {
	head := queue[0]
	queue = queue[1:]
	// step 3: 拓展相邻节点
	// pop 出的节点的相邻节点，加入队列并在 distance 中存储距离
	for _, neighbor := range head.Neighbors {
		if _, ok := distance[neighbor]; ok {
			continue
		}
		distance[neighbor] = distance[head] + 1
		queue = append(queue, neighbor)
	}
}

func CloneGraph(node *UndirectedGraphNode) *UndirectedGraphNode {
	if node == nil {
		return nil
	}
	nodeSet := findNodesByBfs(node)
	mapping := copyNodes(nodeSet)
	copyEdges(nodeSet, mapping)
	return mapping[node]
}

type nodeSet map[*UndirectedGraphNode]bool

func findNodesByBfs(node *UndirectedGraphNode) nodeSet {
	queue := []*UndirectedGraphNode{node}
	visited := nodeSet{
		node: true,
	}
	for len(queue) > 0 {
		curNode := queue[0]
		queue = queue[1:]
		for _, neighbor := range curNode.Neighbors {
			if visited[neighbor] {
				continue
			}
			queue = append(queue, neighbor)
			visited[neighbor] = true
		}
	}
	return visited
}

func copyNodes(nodeSet nodeSet) map[*UndirectedGraphNode]*UndirectedGraphNode {
	mapping := make(map[*UndirectedGraphNode]*UndirectedGraphNode)
	for node := range nodeSet {
		mapping[node] = &UndirectedGraphNode{
			Label: node.Label,
		}
	}
	return mapping
}

func copyEdges(nodeSet nodeSet, mapping map[*UndirectedGraphNode]*UndirectedGraphNode) {
	for node := range nodeSet {
		newNode := mapping[node]
		for _, neighbor := range node.Neighbors {
			newNeighbor := mapping[neighbor]
			newNode.Neighbors = append(newNode.Neighbors, newNeighbor)
		}
	}
}

func FindNodesByBfsWithLevel(node *UndirectedGraphNode) nodeSet {
	queue := []*UndirectedGraphNode{node}
	visited := nodeSet{
		node: true,
	}
	for len(queue) > 0 {
   
    // 获取当前层的节点数量
    levelSize := len(queue)
		for i := 0; i < levelSize; i++ {
			curNode := queue[0]
			queue = queue[1:]
			for _, neighbor := range curNode.Neighbors {
				if visited[neighbor] {
					continue
				}
				visited[neighbor] = true
				queue = append(queue, neighbor)
			}
		}
	}
	return visited
}

func LadderLength(start string, end string, dict map[string]struct{}) int {
	dict[end] = struct{}{}
	queue := []string{start}
	visited := map[string]bool{
		start: true,
	}

	length := 1
	for len(queue) > 0 {
		length++
    levelSize := len(queue)
		for i := 0; i < levelSize; i++ {
			word := queue[0]
			queue = queue[1:]
			for _, nextWord := range getNextWords(word, dict) {
				if visited[nextWord] {
					continue
				}
				if nextWord == end {
					return length
				}
				visited[nextWord] = true
				queue = append(queue, nextWord)
			}
		}
	}

	return 0
}

func getNextWords(word string, dict map[string]struct{}) []string {
	alphabet := []rune{}
	for r := 'a'; r <= 'z'; r++ {
		alphabet = append(alphabet, r)
	}

	nextWords := []string{}
	for i, v := range word {
		left, right := word[:i], word[i+1:]
		for _, r := range alphabet {
			if v == r {
				continue
			}
			newWord := left + string(r) + right
			if _, ok := dict[newWord]; ok {
				nextWords = append(nextWords, newWord)
			}
		}
	}
	return nextWords
}

func NumIslands(grid [][]bool) int {
	if len(grid) == 0 || len(grid[0]) == 0 {
		return 0
	}
	islands := 0
	visited := map[Coord]bool{}

	for i, row := range grid {
		for j, v := range row {
			p := Coord{i, j}
			if v && !visited[p] {
				islands++
				bfs(grid, p, visited)
			}
		}
	}

	return islands
}

func bfs(grid [][]bool, p Coord, visited map[Coord]bool) {
	queue := []Coord{p}
	visited[p] = true
	for len(queue) > 0 {
		curP := queue[0]
		queue = queue[1:]
		for _, d := range Directions {
			nextP := Coord{
				x: curP.x + d.x,
				y: curP.y + d.y,
			}
			if !nextP.isValid(grid, visited) {
				continue
			}
			queue = append(queue, nextP)
			visited[nextP] = true
		}
	}
}

// 上下左右
var Directions = []Coord{
	{-1, 0},
	{1, 0},
	{0, -1},
	{0, 1},
}

type Coord struct {
	x, y int
}

func (p Coord) isValid(grid [][]bool, visited map[Coord]bool) bool {
	n, m := len(grid), len(grid[0])
	if p.x < 0 || p.x >= n {
		return false
	}
	if p.y < 0 || p.y >= m {
		return false
	}
	if visited[p] {
		return false
	}
	return grid[p.x][p.y]
}

func ShortestPath(grid [][]bool, source *Point, destination *Point) int {
	queue := []Point{*source}
	cellToDisMap := map[Point]int{
		*source: 0,
	}

	for len(queue) > 0 {
		curP := queue[0]
		queue = queue[1:]
		if curP == *destination {
			return cellToDisMap[curP]
		}
		for _, offset := range Offsets {
			newP := Point{
				X: curP.X + offset.X,
				Y: curP.Y + offset.Y,
			}
			if !isValid(newP, grid, cellToDisMap) {
				continue
			}
			queue = append(queue, newP)
			cellToDisMap[newP] = cellToDisMap[curP] + 1
		}
	}
	return -1
}

func TopSort(graph []*DirectedGraphNode) []*DirectedGraphNode {
	order := make([]*DirectedGraphNode, 0, len(graph))
	indegree := make(map[*DirectedGraphNode]int, len(graph))
	for _, node := range graph {
		for _, neighbor := range node.Neighbors {
			indegree[neighbor]++
		}
	}

	queue := []*DirectedGraphNode{}
	for _, node := range graph {
		if _, ok := indegree[node]; !ok {
			queue = append(queue, node)
			order = append(order, node)
		}
	}

	for len(queue) > 0 {
		head := queue[0]
		queue = queue[1:]
		for _, neighbor := range head.Neighbors {
			indegree[neighbor]--
			if indegree[neighbor] == 0 {
				queue = append(queue, neighbor)
				order = append(order, neighbor)
			}
		}
	}

	return order
}

func CanFinish(numCourses int, prerequisites [][]int) bool {
	indegree := make(map[int]int)
	dependencies := make(map[int][]int)
	for _, pair := range prerequisites {
		indegree[pair[0]]++
		if _, ok := indegree[pair[1]]; !ok {
			indegree[pair[1]] = 0
		}
		dependencies[pair[1]] = append(dependencies[pair[1]], pair[0])
	}

	queue := make([]int, 0)
	for course, cnt := range indegree {
		if cnt == 0 {
			queue = append(queue, course)
		}
	}

	for len(queue) > 0 {
		head := queue[0]
		queue = queue[1:]

		for _, v := range dependencies[head] {
			indegree[v]--
			if indegree[v] == 0 {
				queue = append(queue, v)
			}
		}
	}

	for _, cnt := range indegree {
		if cnt > 0 {
			return false
		}
	}
	return true
}

func FindOrder (numCourses int, prerequisites [][]int) []int {
	// 构建图，代表（先修课->多个后修课）的映射
	graph := map[int][]int{}
	// 每个点的入度
	inDegree := map[int]int{}
	for _, v := range prerequisites {
		graph[v[1]] = append (graph[v[1]], v[0])
		inDegree[v[0]]++
	}
	queue := []int{}
	for i := 0; i < numCourses; i++ {
		if _, ok := inDegree[i]; !ok {
			queue = append (queue, i)
		}
	}

	numChoose := 0
	topoOrder := make ([]int, 0, numCourses)
	for len (queue) > 0 {
		nowPos := queue[0]
		queue = queue[1:]
		topoOrder = append (topoOrder, nowPos)
		numChoose++
		for _, v := range graph[nowPos] {
			inDegree[v]--
			if inDegree[v] == 0 {
				queue = append (queue, v)
			}
		}
	}

	if numChoose != numCourses {
		return []int{}
	}
	return topoOrder
}

func SequenceReconstruction (org []int, seqs [][]int) bool {
	graph := map[int][]int{}
	inDegree := map[int]int{}
	for _, seq := range seqs {
		for i, node := range seq {
			if i == 0 {
				if _, ok := inDegree[node]; !ok {
					inDegree[node] = 0
				}
			} else {
				graph[seq[i-1]] = append (graph[seq[i-1]], node)
				inDegree[node]++
			}
		}
	}

	queue := []int{}
	for k, v := range inDegree {
		if v == 0 {
			queue = append (queue, k)
		}
	}

	topo := []int{}
	numChoose := 0
	for len (queue) > 0 {
		if len (queue) > 1 {
			return false
		}
		nowPos := queue[0]
		queue = queue[1:]
		topo = append (topo, nowPos)
		numChoose++

		for _, v := range graph[nowPos] {
			inDegree[v]--
			if inDegree[v] == 0 {
				queue = append (queue, v)
			}
		}
	}

	if numChoose != len (org) {
		return false
	}
	return fmt.Sprint (org) == fmt.Sprint (topo)
}

func AlienOrder (words []string) string {
	// 初始化图
	graph := map[byte][]byte{}
	for _, word := range words {
		for _, r := range word {
			graph[byte (r)] = []byte{}
		}
	}

	// 初始化图中的边
	for i := 0; i < len (words)-1; i++ {
		min := len (words[i])
		if len (words[i+1]) < min {
			min = len (words[i+1])
		}

		for j := 0; j < min; j++ {
			if words[i][j] != words[i+1][j] {
				graph[words[i][j]] = append (graph[words[i][j]], words[i+1][j])
				break
			}
			if j == min-1 {
				if len (words[i]) > len (words[j]) {
					return ""
				}
			}
		}
	}

	// 初始化入度
	inDegrees := map[byte]int{}
	for node := range graph {
		inDegrees[node] = 0
	}
	for _, neighbors := range graph {
		for _, neighbor := range neighbors {
			inDegrees[neighbor]++
		}
	}

	queue := &ByteHeap{}
	heap.Init (queue)
	for node, inDegree := range inDegrees {
		if inDegree == 0 {
			heap.Push (queue, node)
		}
	}

	topoOrder := []byte{}
	for queue.Len () > 0 {
		curNode := heap.Pop (queue). (byte)
		topoOrder = append (topoOrder, curNode)

		for _, neighbor := range graph[curNode] {
			inDegrees[neighbor]--
			if inDegrees[neighbor] == 0 {
				heap.Push (queue, neighbor)
			}
		}
	}

	if len (topoOrder) != len (graph) {
		return ""
	}

	return string (topoOrder)
}

// A ByteHeap is a min-heap of bytes.
type ByteHeap []byte

func (h ByteHeap) Len () int           { return len (h) }
func (h ByteHeap) Less (i, j int) bool { return h[i] < h[j] }
func (h ByteHeap) Swap (i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *ByteHeap) Push (x any) {
	// Push and Pop use pointer receivers because they modify the slice's length,
	// not just its contents.
	*h = append (*h, x.(byte))
}

func (h *ByteHeap) Pop () any {
	old := *h
	n := len (old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}