DFS

AcWing 842. 排列数字

package main

import (
	"bufio"
	"fmt"
	"os"
)

var (
	path []int
	vis  = 0
)

func _debug() {
	path = []int{}
	vis = 0
	n := ri()
	back(n)
}

func back(n int) {
	if len(path) == n {
		for _, x := range path {
			fmt.Fprint(out, x, " ")
		}
		fmt.Fprint(out, "\\n")
		return
	}

	for j := 1; j <= n; j++ {
		if (vis>>j)&1 == 1 {
			continue
		}
		path = append(path, j)
		vis |= (1 << j)

		back(n)

		path = path[:len(path)-1]
		vis &= ^(1 << j)
	}
}

// ===== ===== fast io ===== =====
// golang fast io from 0x3F <https://github.com/EndlessCheng/codeforces-go/>

const eof = 0

var (
	_i, _n, buf = 0, 0, make([]byte, 1<<12) // 4KB rc rs rsn
)

func rc() byte { // faster read one byte
	if _i == _n {
		_n, _ = os.Stdin.Read(buf)
		if _n == 0 { // EOF
			return eof
		}
		_i = 0
	}
	b := buf[_i]
	_i++
	return b
}

func ri() (x int) { // faster read int, support negative
	neg := false
	b := rc()
	for ; '0' > b || b > '9'; b = rc() {
		// 某些多组数据的题目，不告诉有多少组数据，那么需要额外判断是否读到了 EOF
		if b == eof {
			return
		}
		if b == '-' {
			neg = true
		}
	}
	for ; '0' <= b && b <= '9'; b = rc() {
		x = x*10 + int(b&15)
	}
	if neg {
		return -x
	}
	return
}

var (
	in *bufio.Reader // 搭配Fscan使用
	// in  *bufio.Scanner
	out *bufio.Writer
)

func main() {
	in = bufio.NewReader(os.Stdin) // 搭配Fscan使用
	out = bufio.NewWriter(os.Stdout)
	defer out.Flush()
	// ===== ===== fast io ===== =====
	_debug()
}

AcWing 843. n-皇后问题

package main

import (
	"bufio"
	"fmt"
	"os"
)

func _debug() {
	n := ri()
	tmp := make([]byte, n)
	for i := range tmp {
		tmp[i] = '.'
	}

	grid := make([][]byte, n)
	for i := range grid {
		grid[i] = make([]byte, n)
		copy(grid[i], tmp)
	}

	dfs(grid, 0, n)
}

func dfs(grid [][]byte, row, n int) {
	if row == n {
		for _, row := range grid {
			fmt.Fprintln(out, string(row))
		}
		fmt.Fprintln(out)
		return
	}

	for i := 0; i < n; i++ {
		if isvalid(grid, row, i, n) {
			grid[row][i] = 'Q'
			dfs(grid, row+1, n)
			grid[row][i] = '.'
		}
	}
}

func isvalid(grid [][]byte, row, col int, n int) bool {
	// 检查列
	for i := 0; i < row; i++ {
		if grid[i][col] == 'Q' {
			return false
		}
	}

	// 检查斜角
	for i, j := row-1, col-1; i >= 0 && j >= 0; i, j = i-1, j-1 {
		if grid[i][j] == 'Q' {
			return false
		}
	}

	// 检查斜角
	// 检查斜角
	for i, j := row-1, col+1; i >= 0 && j < n; i, j = i-1, j+1 {
		if grid[i][j] == 'Q' {
			return false
		}
	}
	return true
}

// ===== ===== fast io ===== =====
// golang fast io from 0x3F <https://github.com/EndlessCheng/codeforces-go/>

const eof = 0

var (
	_i, _n, buf = 0, 0, make([]byte, 1<<12) // 4KB rc rs rsn

	outs = make([]byte, 0, 1e6*22) // 或者创建一个全局 array _o，然后 outS := _o[:0]（效率几乎一样）
	tmps = [64]byte{}              // 可根据绝对值的十进制长度的上限调整
)

func rc() byte { // faster read one byte
	if _i == _n {
		_n, _ = os.Stdin.Read(buf)
		if _n == 0 { // EOF
			return eof
		}
		_i = 0
	}
	b := buf[_i]
	_i++
	return b
}

func ri() (x int) { // faster read int, support negative
	neg := false
	b := rc()
	for ; '0' > b || b > '9'; b = rc() {
		// 某些多组数据的题目，不告诉有多少组数据，那么需要额外判断是否读到了 EOF
		if b == eof {
			return
		}
		if b == '-' {
			neg = true
		}
	}
	for ; '0' <= b && b <= '9'; b = rc() {
		x = x*10 + int(b&15)
	}
	if neg {
		return -x
	}
	return
}

var (
	in *bufio.Reader // 搭配Fscan使用
	out *bufio.Writer
)

func main() {
	in = bufio.NewReader(os.Stdin) // 搭配Fscan使用
	out = bufio.NewWriter(os.Stdout)
	defer out.Flush()
	// ===== ===== fast io ===== =====
	_debug()
}

BFS

AcWing 844. 走迷宫

package main

import (
	"bufio"
	"fmt"
	"os"
)

func _debug() {
	n, m := ri(), ri()

	grid := make_two_dimen(n, m)

	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			grid[i][j] = ri()
		}
	}
	bfs(grid)
}

func bfs(grid [][]int) {
	q := [][]int{}

	dist := make_two_dimen_with_val(len(grid), len(grid[0]), -1)

	q = append(q, []int{0, 0})
	dist[0][0] = 0

	for len(q) != 0 {
		x := q[0][0]
		y := q[0][1]

		q = q[1:]

		for _, d := range directions {
			dx := x + d[0]
			dy := y + d[1]
			if isok(grid, dx, dy) && grid[x][y] == 0 && dist[dx][dy] == -1 {
				dist[dx][dy] = dist[x][y] + 1
				q = append(q, []int{dx, dy})
			}
		}
	}
	fmt.Fprintln(out, dist[len(grid)-1][len(grid[0])-1])
}

var directions = [4][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}} // 四个遍历方向
func isok(grid [][]int, i, j int) bool { // 判断是否在二维数组越界
	return i >= 0 && i < len(grid) && j >= 0 && j < len(grid[0])
}

// 创建指定维度的二维数组
// n: rows; m: cols
func make_two_dimen(n, m int) (ans [][]int) {
	ans = make([][]int, n)
	for i := range ans {
		ans[i] = make([]int, m)
	}
	return
}

// 创建指定维度的二维数组，并赋特定值
func make_two_dimen_with_val(n, m, val int) (ans [][]int) {
	tmp := make([]int, m)
	for i := range tmp {
		tmp[i] = val
	}

	ans = make([][]int, n)
	for i := range ans {
		ans[i] = make([]int, m)
		copy(ans[i], tmp)
	}
	return
}

// ===== ===== fast io ===== =====
// golang fast io from 0x3F <https://github.com/EndlessCheng/codeforces-go/>

const eof = 0

var (
	_i, _n, buf = 0, 0, make([]byte, 1<<12) // 4KB rc rs rsn

	outs = make([]byte, 0, 1e6*22) // 或者创建一个全局 array _o，然后 outS := _o[:0]（效率几乎一样）
	tmps = [64]byte{}              // 可根据绝对值的十进制长度的上限调整
)

func rc() byte { // faster read one byte
	if _i == _n {
		_n, _ = os.Stdin.Read(buf)
		if _n == 0 { // EOF
			return eof
		}
		_i = 0
	}
	b := buf[_i]
	_i++
	return b
}

func ri() (x int) { // faster read int, support negative
	neg := false
	b := rc()
	for ; '0' > b || b > '9'; b = rc() {
		// 某些多组数据的题目，不告诉有多少组数据，那么需要额外判断是否读到了 EOF
		if b == eof {
			return
		}
		if b == '-' {
			neg = true
		}
	}
	for ; '0' <= b && b <= '9'; b = rc() {
		x = x*10 + int(b&15)
	}
	if neg {
		return -x
	}
	return
}

var (
	in *bufio.Reader // 搭配Fscan使用
	out *bufio.Writer
)

func main() {
	in = bufio.NewReader(os.Stdin) // 搭配Fscan使用
	out = bufio.NewWriter(os.Stdout)
	defer out.Flush()
	// ===== ===== fast io ===== =====
	_debug()
}

AcWing 845. 八数码

package main

import (
	"bufio"
	"fmt"
	"os"
	"strings"
)

func _debug() {
	start := make([]byte, 9)
	for i := range start {
		start[i] = rsn(1)[0]
	}

	q := [][]byte{}
	dist := map[string]int{}

	q = append(q, start)
	dist[string(start)] = 0

	for len(q) != 0 {
		cur := q[0] // []byte
		q = q[1:]
		distance := dist[string(cur)]

		if string(cur) == "12345678x" {
			fmt.Fprintln(out, distance)
			return
		}

		idx := strings.Index(string(cur), "x")
		x := idx / 3
		y := idx % 3

		for _, d := range directions {
			dx := x + d[0]
			dy := y + d[1]

			if !_isok(dx, dy, 3, 3) {
				continue
			}
			idx_new := dx*3 + dy

			cur[idx], cur[idx_new] = cur[idx_new], cur[idx]
			if _, ok := dist[string(cur)]; !ok {
				dist[string(cur)] = distance + 1
				tmp := append([]byte{}, cur...)
				q = append(q, tmp) // copy and append
			}
			cur[idx], cur[idx_new] = cur[idx_new], cur[idx]
		}
	}
	fmt.Fprintln(out, -1)
}

var directions = [4][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}} // 四个遍历方向

func _isok(i, j int, n, m int) bool {
	return i >= 0 && j >= 0 && i < n && j < m
}

// ===== ===== fast io ===== =====
// golang fast io from 0x3F <https://github.com/EndlessCheng/codeforces-go/>
const eof = 0

var (
	_i, _n, buf = 0, 0, make([]byte, 1<<12) // 4KB rc rs rsn

	outs = make([]byte, 0, 1e6*22) // 或者创建一个全局 array _o，然后 outS := _o[:0]（效率几乎一样）
	tmps = [64]byte{}              // 可根据绝对值的十进制长度的上限调整
)

func rc() byte { // faster read one byte
	if _i == _n {
		_n, _ = os.Stdin.Read(buf)
		if _n == 0 { // EOF
			return eof
		}
		_i = 0
	}
	b := buf[_i]
	_i++
	return b
}

// 读一个长度为 n 的仅包含小写/大写字母的字符串，必要时进行修改
func rsn(n int) []byte {
	b := rc()
	// 只读取大小写字母和数字
	for ; !('a' <= b && b <= 'z') && !('A' <= b && b <= 'Z') && !('0' <= b && b <= '9'); b = rc() { // 'A' 'Z'
	}
	s := make([]byte, 0, n)
	s = append(s, b)
	for i := 1; i < n; i++ {
		s = append(s, rc())
	}
	return s
}

var (
	in *bufio.Reader // 搭配Fscan使用
	out *bufio.Writer
)

func main() {
	in = bufio.NewReader(os.Stdin) // 搭配Fscan使用
	out = bufio.NewWriter(os.Stdout)
	defer out.Flush()
	// ===== ===== fast io ===== =====
	_debug()
}

树与图的深度优先遍历

AcWing 846. 树的重心

package main

import (
	"bufio"
	"fmt"
	"os"
)

func _debug() {
	const eof = 0
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()
	_i, _n, buf := 0, 0, make([]byte, 1<<12) // 4KB

	// 读一个字符
	rc := func() byte {
		if _i == _n {
			_n, _ = os.Stdin.Read(buf)
			if _n == 0 { // EOF
				return eof
			}
			_i = 0
		}
		b := buf[_i]
		_i++
		return b
	}

	// 读一个整数，支持负数
	ri := func() (x int) {
		neg := false
		b := rc()
		for ; '0' > b || b > '9'; b = rc() {
			// 某些多组数据的题目，不告诉有多少组数据，那么需要额外判断是否读到了 EOF
			if b == eof {
				return
			}
			if b == '-' {
				neg = true
			}
		}
		for ; '0' <= b && b <= '9'; b = rc() {
			x = x*10 + int(b&15)
		}
		if neg {
			return -x
		}
		return
	}
	_ = []interface{}{rc, ri}

	n := ri()

	g := make([][]int, n+1)

	for i := 0; i < n-1; i++ {
		a, b := ri(), ri()
		g[a] = append(g[a], b)
		g[b] = append(g[b], a)
	}

	st := make([]bool, n+1)

	dfs(1, st, g)

	fmt.Fprintln(out, ans)
}

var (
	ans int = 1<<31 - 1
)

func dfs(u int, st []bool, g [][]int) int {
	res := 0
	st[u] = true
	sum := 1

	for _, x := range g[u] {
		if !st[x] {
			s := dfs(x, st, g)
			res = max_i(res, s)
			sum += s
		}
	}

	res = max_i(res, len(g)-1-sum) // n-sum
	ans = min_i(res, ans)
	return sum
}

func max_i(a, b int) int {
	if a < b {
		return b
	}
	return a
}

func min_i(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	_debug()
}

树与图的广度优先遍历

AcWing 847. 图中点的层次

package main

import (
	"bufio"
	"fmt"
	"os"
)

func _debug() {
	n, m := ri(), ri()

	mp := map[int][]int{}

	vis := make([]bool, n+1)

	for ; m > 0; m-- {
		a, b := ri(), ri()
		mp[a] = append(mp[a], b)
	}

	q := []int{}
	q = append(q, 1)
	vis[1] = true

	dist := 0
	for len(q) != 0 {
		size := len(q)

		for i := 0; i < size; i++ {
			cur := q[0]
			q = q[1:]
			vis[cur] = true

			if cur == n {
				fmt.Fprintln(out, dist)
				return
			}

			for _, x := range mp[cur] {
				if vis[x] {
					continue
				}
				q = append(q, x)
			}
		}
		dist++
	}
	fmt.Fprintln(out, -1)
}

// ===== ===== fast io ===== =====
// golang fast io from 0x3F <https://github.com/EndlessCheng/codeforces-go/>

const eof = 0

var (
	_i, _n, buf = 0, 0, make([]byte, 1<<12) // 4KB rc rs rsn

	outs = make([]byte, 0, 1e6*22) // 或者创建一个全局 array _o，然后 outS := _o[:0]（效率几乎一样）
	tmps = [64]byte{}              // 可根据绝对值的十进制长度的上限调整
)

func rc() byte { // faster read one byte
	if _i == _n {
		_n, _ = os.Stdin.Read(buf)
		if _n == 0 { // EOF
			return eof
		}
		_i = 0
	}
	b := buf[_i]
	_i++
	return b
}

func ri() (x int) { // faster read int, support negative
	neg := false
	b := rc()
	for ; '0' > b || b > '9'; b = rc() {
		// 某些多组数据的题目，不告诉有多少组数据，那么需要额外判断是否读到了 EOF
		if b == eof {
			return
		}
		if b == '-' {
			neg = true
		}
	}
	for ; '0' <= b && b <= '9'; b = rc() {
		x = x*10 + int(b&15)
	}
	if neg {
		return -x
	}
	return
}

var (
	in *bufio.Reader // 搭配Fscan使用
	out *bufio.Writer
)

func main() {
	in = bufio.NewReader(os.Stdin) // 搭配Fscan使用
	out = bufio.NewWriter(os.Stdout)
	defer out.Flush()
	// ===== ===== fast io ===== =====
	_debug()
}

拓扑排序

AcWing 848. 有向图的拓扑序列