search.go

package copypasta

import (
	"math/bits"
	"slices"
	"sort"
)

/* 状态空间
一个实际问题的各种可能情况构成的集合
由小及大：当状态空间位于边界上或某个小范围内等特殊情形，该状态空间的解往往是已知的。
若能将此解的应用场景扩大到原问题的状态空间，并且扩展过程的每个步骤具有相似性，就可以考虑使用递推或递归求解。
换句话说，程序在每个步骤上应该面对相同种类的问题，这些问题都是原问题的一个「子问题」，可能仅在规模或者某些限制条件上有所区别，并且能够使用「求解原问题的程序」进行求解。

Self-Avoiding Walk https://mathworld.wolfram.com/Self-AvoidingWalk.html

COUNTING SELF-AVOIDING WALKS https://arxiv.org/pdf/1304.7216.pdf

https://oeis.org/A096969 Number of directed Hamiltonian paths in (n X n)-grid graph
1, 8, 40, 552, 8648, 458696, 27070560, 6046626568, 1490832682992, 1460089659025264, 1573342970540617696, 6905329711608694708440, 33304011435341069362631160, 663618176813467308855850585056, 14527222735920532980525200234503048

https://oeis.org/A236753 Number of simple (non-intersecting) directed paths in (n X n)-grid graph
1, 28, 653, 28512, 3060417, 873239772, 687430009069, 1532025110398168, 9829526954625359697, 183563561823425961932572, 10056737067604248527218979485, 1626248896102138091401810358337184

https://oeis.org/A001411 Number of n-step self-avoiding walks on square lattice
1, 4, 12, 36, 100, 284, 780, 2172, 5916, 16268, 44100, 120292, 324932, 881500, 2374444, 6416596, 17245332, 46466676, 124658732, 335116620, 897697164, 2408806028, 6444560484, 17266613812, 46146397316, 123481354908, 329712786220, 881317491628

https://oeis.org/A046170 Number of self-avoiding walks on a 2-D lattice of length n which start at the origin, take first step in the {+1,0} direction and whose vertices are always nonnegative in x and y
1, 2, 5, 12, 30, 73, 183, 456, 1151, 2900, 7361, 18684, 47652, 121584, 311259, 797311, 2047384, 5260692, 13542718, 34884239, 89991344, 232282110, 600281932, 1552096361, 4017128206, 10401997092, 26957667445, 69892976538

https://oeis.org/A007764 Number of non-intersecting (or self-avoiding) rook paths joining opposite corners of an n X n grid
1, 2, 12, 184, 8512, 1262816, 575780564, 789360053252, 3266598486981642, 41044208702632496804, 1568758030464750013214100, 182413291514248049241470885236, 64528039343270018963357185158482118, 69450664761521361664274701548907358996488

Number of simple (non-intersecting) directed paths [of length n] in (n X n)-grid graph
1, 8, 44, 232, 972, 4008, 14932, 55104, 191068, 657848 [10], 2176716, 7157296, 22902052, 72898328, 227471396, 706797600, 2162946116

https://oeis.org/A038373 Number of n-step self-avoiding paths on quadrant grid starting at quadrant origin
1, 2, 4, 10, 24, 60, 146, 366, 912, 2302, 5800, 14722, 37368, 95304, 243168, 622518, 1594622, 4094768, 10521384, 27085436, 69768478, 179982688, 464564220, 1200563864, 3104192722, 8034256412, 20803994184, 53915334890, 139785953076, 362681515714, 941361260956, 2444866458524, 6351963691964

Number of n-step self-avoiding paths on quadrant grid starting at center
1, 2, 8, 20, 64, 172, 520, 1432, 4176, 11504, 32824, 90024, 252992, 690596, 1919328, 5217716, 14380256, 38957328, 106676600

https://oeis.org/A145157 Number of Greek-key tours on an n X n board; i.e., self-avoiding walks on n X n grid starting in top left corner
1, 2, 8, 52, 824, 22144, 1510446, 180160012, 54986690944, 29805993260994, 41433610713353366, 103271401574007978038, 660340630211753942588170, 7618229614763015717175450784, 225419381425094248494363948728158

https://oeis.org/A000532 Number of Hamiltonian paths from NW to SW corners in an n X n grid
1, 1, 2, 8, 86, 1770, 88418, 8934966, 2087813834, 1013346943033, 1111598871478668, 2568944901392936854, 13251059359839620127088, 145194816279817259193401518, 3524171261632305641165676374930

https://oeis.org/A000129 Pell numbers: a(0) = 0, a(1) = 1; for n > 1, a(n) = 2*a(n-1) + a(n-2)
https://en.wikipedia.org/wiki/Pell_number
Number of lattice paths from (0,0) to the line x=n-1 consisting of U=(1,1), D=(1,-1) and H=(2,0) steps (i.e., left factors of Grand Schroeder paths)
for example, a(3)=5, counting the paths H, UD, UU, DU and DD
https://oeis.org/A048739 A000129 的前缀和

https://oeis.org/A001333 Number of n-step non-selfintersecting paths starting at (0,0) with steps of types (1,0), (-1,0) or (0,1)
https://codeforces.com/problemset/problem/954/F

*/

/* 回溯

子集（也可以用二进制枚举做）
- [78. 子集](https://leetcode.cn/problems/subsets/)
- [784. 字母大小写全排列](https://leetcode.cn/problems/letter-case-permutation/) 1342
- [1286. 字母组合迭代器](https://leetcode.cn/problems/iterator-for-combination/) 1591
- [LCP 51. 烹饪料理](https://leetcode.cn/problems/UEcfPD/)
- [2397. 被列覆盖的最多行数](https://leetcode.cn/problems/maximum-rows-covered-by-columns/) 1719
- [2212. 射箭比赛中的最大得分](https://leetcode.cn/problems/maximum-points-in-an-archery-competition/) 1869
- [2151. 基于陈述统计最多好人数](https://leetcode.cn/problems/maximum-good-people-based-on-statements/) 1980
- [2959. 关闭分部的可行集合数目](https://leetcode.cn/problems/number-of-possible-sets-of-closing-branches/) 2077
- [1601. 最多可达成的换楼请求数目](https://leetcode.cn/problems/maximum-number-of-achievable-transfer-requests/) 2119
- [1617. 统计子树中城市之间最大距离](https://leetcode.cn/problems/count-subtrees-with-max-distance-between-cities/) 2309
- [320. 列举单词的全部缩写](https://leetcode.cn/problems/generalized-abbreviation/)（会员题）
https://codeforces.com/problemset/problem/550/B 1400
https://codeforces.com/problemset/problem/962/C 1400

组合
- [77. 组合](https://leetcode.cn/problems/combinations/)
- [216. 组合总和 III](https://leetcode.cn/problems/combination-sum-iii/)
- [22. 括号生成](https://leetcode.cn/problems/generate-parentheses/)
- [301. 删除无效的括号](https://leetcode.cn/problems/remove-invalid-parentheses/)

分割
- [131. 分割回文串](https://leetcode.cn/problems/palindrome-partitioning/)
- [306. 累加数](https://leetcode.cn/problems/additive-number/)
- [93. 复原 IP 地址](https://leetcode.cn/problems/restore-ip-addresses/)
- [2698. 求一个整数的惩罚数](https://leetcode.cn/problems/find-the-punishment-number-of-an-integer/) 1679

排列（部分题目可以用状压 DP 继续优化）
- [46. 全排列](https://leetcode.cn/problems/permutations/)
- [51. N 皇后](https://leetcode.cn/problems/n-queens/)
- [52. N 皇后 II](https://leetcode.cn/problems/n-queens-ii/)
- [2850. 将石头分散到网格图的最少移动次数](https://leetcode.cn/problems/minimum-moves-to-spread-stones-over-grid/) 2001
- [1307. 口算难题](https://leetcode.cn/problems/verbal-arithmetic-puzzle/) 2250
- [2014. 重复 K 次的最长子序列](https://leetcode.cn/problems/longest-subsequence-repeated-k-times/) 2558
- [267. 回文排列 II](https://leetcode.cn/problems/palindrome-permutation-ii/)（会员题）
网格 https://atcoder.jp/contests/abc326/tasks/abc326_d

爆搜+剪枝
- [3211. 生成不含相邻零的二进制字符串](https://leetcode.cn/problems/generate-binary-strings-without-adjacent-zeros/)
- [79. 单词搜索](https://leetcode.cn/problems/word-search/)
- [212. 单词搜索 II](https://leetcode.cn/problems/word-search-ii/)
- [140. 单词拆分 II](https://leetcode.cn/problems/word-break-ii/)
- [473. 火柴拼正方形](https://leetcode.cn/problems/matchsticks-to-square/)
- [488. 祖玛游戏](https://leetcode.cn/problems/zuma-game/)
- [638. 大礼包](https://leetcode.cn/problems/shopping-offers/)
- [1255. 得分最高的单词集合](https://leetcode.cn/problems/maximum-score-words-formed-by-letters/) 1882
- [面试题 17.25. 单词矩阵](https://leetcode.cn/problems/word-rectangle-lcci/)

关于可行性剪枝，见 https://leetcode.cn/problems/combination-sum/solutions/2747858/liang-chong-fang-fa-xuan-huo-bu-xuan-mei-mhf9/

https://www.luogu.com.cn/problem/P1379
https://codeforces.com/problemset/problem/429/C
爆搜 https://atcoder.jp/contests/abc233/tasks/abc233_c
https://atcoder.jp/contests/abc319/tasks/abc319_c
https://atcoder.jp/contests/abc197/tasks/abc197_c

https://oeis.org/A038206 Can express a(n) with the digits of a(n)^2 in order, only adding plus signs
- LC2698 https://leetcode.cn/problems/find-the-punishment-number-of-an-integer/
https://oeis.org/A104113 Numbers which when chopped into one, two or more parts, added and squared result in the same number

不允许重复的排列：见 nextPermutation
*/
func searchCollection() {
	// 指数型，即 n 层循环
	// https://codeforces.com/contest/459/problem/C
	loopAny := func(n, low, up int) { // or lows ups []int
		vals := make([]int, n)
		var f func(int)
		f = func(p int) {
			if p == n {
				// do vals...

				return
			}
			for vals[p] = low; vals[p] <= up; vals[p]++ {
				f(p + 1)
			}
		}
		f(0)
	}

	// 任意子集：从集合 1~n 中不重复地选取任意个元素
	// 位运算写法见下面的 loopCollection
	// 模板题 https://ac.nowcoder.com/acm/contest/6913/A
	chooseAny := func(n int) {
		{
			cnt := 0
			chosen := []int{}
			var f func(int)
			f = func(p int) {
				if p == n+1 {
					// do chosen... or just cnt++
					cnt++
					return
				}

				// 剪枝：能否继续...

				// 不选 p
				f(p + 1)

				// 选 p
				// 剪枝：能否选 p（是否与 chosen 中的元素冲突等）...

				chosen = append(chosen, p)
				f(p + 1) // 如果可以重复，这里写 f(p)
				chosen = chosen[:len(chosen)-1]
			}
			f(1)
		}

		{
			cnt := 0
			used := make([]bool, n+1)
			var f func(int)
			f = func(p int) {
				if p == n+1 {
					// do used... or just cnt++
					cnt++
					return
				}

				// 剪枝：能否继续...

				// 不选 p
				f(p + 1)

				// 选 p
				// 剪枝：能否选 p（是否与 used 中的元素冲突等）...

				used[p] = true
				f(p + 1)
				used[p] = false
			}
			f(1)
		}
	}

	// 部分子集：从集合 1~n 中不重复地选取至多 m 个元素 (0<=m<=n)
	chooseAtMost := func(n, m int) {
		chosen := []int{}
		var f func(int)
		f = func(p int) {
			if len(chosen) > m || len(chosen)+n-p+1 < m {
				return
			}
			if p == n+1 {
				// do chosen...

				return
			}
			// 不选 p
			f(p + 1)
			// 选 p
			chosen = append(chosen, p)
			f(p + 1)
			chosen = chosen[:len(chosen)-1]
		}
		f(1)
	}

	// 可重复组合
	// 以 LC1467 为例 https://leetcode.cn/problems/probability-of-a-two-boxes-having-the-same-number-of-distinct-balls/
	// 每个数至多可选 upper[i] 个，从中随机选择 m 个（m<=∑upper），求满足题设条件的概率
	// 枚举每个数选了多少个，根据乘法原理计算某个组合的个数（例如 upper=[4,3,1]，m=4，其中选2个0，2个1就有C(4,2)*C(3,2)种）
	// 总数有 C(∑upper,m) 种
	searchCombinations := func(upper []int) float64 {
		const mx = 48
		C := [mx + 1][mx + 1]int{}
		for i := 0; i <= mx; i++ {
			C[i][0], C[i][i] = 1, 1
			for j := 1; j < i; j++ {
				C[i][j] = C[i-1][j-1] + C[i-1][j]
			}
		}

		n := len(upper)
		sum := 0
		for _, v := range upper {
			sum += v
		}
		sum /= 2

		okWays := 0
		var f func(p, s, cntL, cntR, ways int)
		f = func(p, s, cntL, cntR, ways int) {
			//if s > sum {
			//	return
			//}
			if p == n {
				// do...
				if s == sum && cntL == cntR {
					okWays += ways
				}
				return
			}
			for i := 0; i <= upper[p] && s+i <= sum; i++ {
				cl, cr := cntL, cntR
				if i > 0 {
					cl++
				}
				if i < upper[p] {
					cr++
				}
				f(p+1, s+i, cl, cr, ways*C[upper[p]][i]) // 乘法原理
			}
		}
		f(0, 0, 0, 0, 1)
		return float64(okWays) / float64(C[2*sum][sum])
	}

	// 排列（不能重复）
	// 即有 n 个位置，从左往右地枚举每个位置上可能出现的值（值必须在 a 中且不能重复）
	// 对比上面的子集搜索，那是对每个位置枚举是否选择（两个分支），而这里每个位置有 n 个分支
	// https://www.luogu.com.cn/problem/P1118
	// LC1307 https://leetcode.cn/problems/verbal-arithmetic-puzzle/
	searchPermutations := func(a []int) bool {
		n := len(a)
		used := 0
		var f func(p, sum int) bool
		f = func(p, sum int) bool {
			//if sum > ... { } // 剪枝
			if p == n {
				// do sum...

				return sum == 0
			}
			// 对每个位置，枚举可能出现的值，跳过已经枚举的值
			for i, v := range a {
				if used>>i&1 > 0 {
					continue
				}
				used |= 1 << i
				// copy sum and do v...
				s := sum
				s += v
				if f(p+1, s) {
					//used[i] = false
					return true
				}
				used ^= 1 << i
			}
			return false
		}
		return f(0, 0)
	}

	//

	// 生成字符串 s 的所有长度至多为 m 的非空子串（去重，按字典序返回）
	// https://codeforces.com/problemset/problem/120/H
	genSubStrings := func(s string, m int) []string {
		ss := []string{}
		var f func(s, sub string)
		f = func(s, sub string) {
			ss = append(ss, sub)
			if len(sub) == m {
				return
			}
			for i, b := range s {
				f(s[i+1:], sub+string(b))
			}
		}
		f(s, "")
		ss = ss[1:] // 去掉空字符串
		slices.Sort(ss)
		j := 0
		for i := 1; i < len(ss); i++ {
			if ss[j] != ss[i] {
				j++
				ss[j] = ss[i]
			}
		}
		return ss[:j+1]
	}

	//

	// 每个位置独立，枚举 [0,limits[i]] 范围内的数
	iterWithLimits := func(limits []int, do func(upp []int) bool) {
		n := len(limits)
		upp := make([]int, n)
		var f func(p int) bool
		f = func(p int) bool {
			if p == n {
				return do(upp)
			}
			for upp[p] = 0; upp[p] <= limits[p]; upp[p]++ {
				if f(p + 1) {
					return true
				}
			}
			return false
		}
		f(0)
	}

	// 每个位置独立，枚举 [0,limits[i]] 范围内的数，且和为 sum
	iterWithLimitsAndSum := func(sum int, limits []int, do func(a []int) bool) {
		n := len(limits)
		a := make([]int, n)
		var f func(int, int) bool
		f = func(p, s int) bool {
			if s > sum {
				return false
			}
			if p == n {
				if s < sum {
					return false
				}
				return do(a)
			}
			for a[p] = 0; a[p] <= limits[p]; a[p]++ {
				if f(p+1, s+a[p]) {
					return true
				}
			}
			return false
		}
		f(0, 0)
	}

	//

	// 从 n 个元素中选择 r 个元素，按字典序生成所有组合，每个组合用下标表示  r <= n
	// 由于实现上直接传入了 indexes，所以在 do 中不能修改 ids。若要修改则代码在传入前需要 copy 一份
	// 参考 https://docs.python.org/3/library/itertools.html#itertools.combinations
	// https://stackoverflow.com/questions/41694722/algorithm-for-itertools-combinations-in-python
	combinations := func(n, r int, do func(ids []int) (Break bool)) {
		ids := make([]int, r)
		for i := range ids {
			ids[i] = i
		}
		if do(ids) {
			return
		}
		for {
			i := r - 1
			for ; i >= 0; i-- {
				if ids[i] != i+n-r {
					break
				}
			}
			if i == -1 {
				return
			}
			ids[i]++
			for j := i + 1; j < r; j++ {
				ids[j] = ids[j-1] + 1
			}
			if do(ids) {
				return
			}
		}
	}

	// 从 n 个元素中选择 k 个元素，允许重复选择同一个元素，按字典序生成所有组合，每个组合用下标表示
	// 由于实现上直接传入了 indexes，所以在 do 中不能修改 ids。若要修改则代码在传入前需要 copy 一份
	// 参考 https://docs.python.org/3/library/itertools.html#itertools.combinations_with_replacement
	// https://en.wikipedia.org/wiki/Combination#Number_of_combinations_with_repetition
	// 方案数 H(n,k)=C(n+k-1,k) https://oeis.org/A059481
	// 相当于长度为 k，元素范围在 [0,n-1] 的非降序列的个数
	combinationsWithRepetition := func(n, k int, do func(ids []int) (Break bool)) {
		ids := make([]int, k)
		if do(ids) {
			return
		}
		for {
			i := k - 1
			for ; i >= 0; i-- {
				if ids[i] != n-1 {
					break
				}
			}
			if i == -1 {
				return
			}
			ids[i]++
			for j := i + 1; j < k; j++ {
				ids[j] = ids[i]
			}
			if do(ids) {
				return
			}
		}
	}

	// 从一个长度为 n 的数组中选择 r 个元素，按字典序生成所有排列，每个排列用下标表示  r <= n
	// 由于实现上直接传入了 indexes，所以在 do 中不能修改 ids。若要修改则代码在传入前需要 copy 一份
	// 参考 https://docs.python.org/3/library/itertools.html#itertools.permutations
	permutations := func(n, r int, do func(ids []int) (Break bool)) {
		ids := make([]int, n)
		for i := range ids {
			ids[i] = i
		}
		if do(ids[:r]) {
			return
		}
		cycles := make([]int, r)
		for i := range cycles {
			cycles[i] = n - i
		}
		for {
			i := r - 1
			for ; i >= 0; i-- {
				cycles[i]--
				if cycles[i] == 0 {
					tmp := ids[i]
					copy(ids[i:], ids[i+1:])
					ids[n-1] = tmp
					cycles[i] = n - i
				} else {
					j := cycles[i]
					ids[i], ids[n-j] = ids[n-j], ids[i]
					if do(ids[:r]) {
						return
					}
					break
				}
			}
			if i == -1 {
				return
			}
		}
	}

	// 生成全排列（不保证字典序，若要用保证字典序的，见 permutations）
	// 会修改原数组
	// Permute the values at index i to len(arr)-1.
	// https://codeforces.com/problemset/problem/910/C
	var _permute func([]int, int, func())
	_permute = func(a []int, i int, do func()) {
		if i == len(a) {
			do()
			return
		}
		_permute(a, i+1, do)
		for j := i + 1; j < len(a); j++ {
			a[i], a[j] = a[j], a[i]
			_permute(a, i+1, do)
			a[i], a[j] = a[j], a[i]
		}
	}
	permuteAll := func(a []int, do func()) { _permute(a, 0, do) }

	// 调用完之后
	// 返回 true：a 修改为其下一个排列（即比 a 大且字典序最小的排列）
	// 返回 false：a 修改为其字典序最小的排列（即 a 排序后的结果）
	// - [31. 下一个排列](https://leetcode.cn/problems/next-permutation/)
	// - [1850. 邻位交换的最小次数](https://leetcode.cn/problems/minimum-adjacent-swaps-to-reach-the-kth-smallest-number/) 2073
	nextPermutation := func(a []int) bool {
		n := len(a)
		i := n - 2
		for i >= 0 && a[i] >= a[i+1] {
			i--
		}
		defer slices.Reverse(a[i+1:])
		if i < 0 {
			return false
		}
		j := n - 1
		for j >= 0 && a[i] >= a[j] {
			j--
		}
		a[i], a[j] = a[j], a[i]
		return true
	}

	// 康托展开 Cantor Expansion
	// 返回所给排列 perm（元素在 [1,n]）的字典序名次（可以从 0 或从 1 开始，具体看代码末尾）
	// 核心思想：对于第 i 个位置，若该位置的数是未出现在其左侧的数中第 k 大的，那么有 (k−1)×(N−i)! 种方案在该位置上比这个排列小
	// 结合康托展开和逆康托展开，可以求出一个排列的下 k 个排列
	// https://zh.wikipedia.org/wiki/%E5%BA%B7%E6%89%98%E5%B1%95%E5%BC%80
	// https://oi-wiki.org/math/cantor/
	// https://www.luogu.com.cn/problem/P5367
	// 有重复元素 LC1830 https://leetcode.cn/problems/minimum-number-of-operations-to-make-string-sorted/
	// https://codeforces.com/problemset/problem/1443/E
	rankPermutation := func(perm []int) int {
		n := len(perm)
		F := make([]int, n)
		F[0] = 1
		for i := 1; i < n; i++ {
			F[i] = F[i-1] * i % mod
		}

		tree := make([]int, n+1)
		add := func(i, val int) {
			for ; i <= n; i += i & -i {
				tree[i] += val
			}
		}
		sum := func(i int) (res int) {
			for ; i > 0; i &= i - 1 {
				res += tree[i]
			}
			return
		}
		for i := 1; i <= n; i++ {
			add(i, 1)
		}

		ans := 0
		for i, v := range perm {
			ans += sum(v-1) * F[n-1-i] % mod
			add(v, -1)
		}
		ans++ // 从 1 开始的排名
		ans %= mod
		return ans
	}

	// 逆康托展开 Inverse Cantor Expansion
	// 返回字典序第 k 小的排列，元素范围为 [1,n]
	// LC60 https://leetcode.cn/problems/permutation-sequence/
	// https://codeforces.com/problemset/problem/1443/E
	kthPermutation := func(n, k int) []int {
		F := make([]int, n)
		F[0] = 1
		for i := 1; i < n; i++ {
			F[i] = F[i-1] * i
		}

		k-- // 如果输入是从 1 开始的，改成从 0 开始
		perm := make([]int, n)
		valid := make([]int, n+1)
		for i := 1; i <= n; i++ {
			valid[i] = 1
		}
		for i := 1; i <= n; i++ {
			order := k/F[n-i] + 1
			for j := 1; j <= n; j++ { // 从 1 开始的排列    TODO 用线段树优化
				order -= valid[j]
				if order == 0 {
					perm = append(perm, j)
					valid[j] = 0
					break
				}
			}
			k %= F[n-i]
		}
		return perm
	}

	// 迭代加深搜索
	// 限制 DFS 深度（不断提高搜索深度）
	// http://poj.org/problem?id=2248

	// 折半枚举/双向搜索 Meet in the middle
	// - [805. 数组的均值分割](https://leetcode.cn/problems/split-array-with-same-average/) 1983
	// - [1755. 最接近目标值的子序列和](https://leetcode.cn/problems/closest-subsequence-sum/) 2364
	// - [2035. 将数组分成两个数组并最小化数组和的差](https://leetcode.cn/problems/partition-array-into-two-arrays-to-minimize-sum-difference/) 2490
	// hqz 的题解 https://leetcode.cn/problems/count-almost-equal-pairs-ii/solutions/2892259/on-log2-ufen-lei-tao-lun-meet-in-the-mid-ysyy/
	// https://codeforces.com/problemset/problem/1006/F 
	// https://atcoder.jp/contests/abc271/tasks/abc271_f 
	// https://leetcode.com/discuss/interview-question/2324457/Google-Online-Assessment-Question
	// O(3^(n/2)) 放A组/放B组/不选 https://www.luogu.com.cn/problem/P3067
	// - https://www.luogu.com.cn/record/88785388
	// https://www.luogu.com.cn/problem/P5194
	// https://www.luogu.com.cn/problem/P4799
	// https://codeforces.com/problemset/problem/327/E
	// https://atcoder.jp/contests/abc184/tasks/abc184_f
	// NEERC 2003 https://codeforces.com/gym/101388 J

	// 折半枚举 - 超大背包问题
	// https://atcoder.jp/contests/abc184/tasks/abc184_f
	bigKnapsack := func(a []int, size int) (ans int) {
		n := len(a)
		if n == 1 {
			if a[0] > size {
				return
			}
			return a[0]
		}

		sumW, ws, end := 0, []int{}, n/2
		var f func(int)
		f = func(p int) {
			if p == end {
				if sumW <= size {
					ws = append(ws, sumW)
				}
				return
			}
			f(p + 1)
			sumW += a[p]
			f(p + 1)
			sumW -= a[p]
		}
		f(0)
		l := ws
		slices.Sort(l)
		// l 去重略

		ws, end = nil, n
		f(n / 2)
		for _, w := range ws {
			// <= size-w 的第一个数（因为 l[0]==0 所以 p 一定非负）
			p := sort.SearchInts(l, size-w+1) - 1
			if l[p]+w > ans {
				ans = l[p] + w
			}
		}
		return
	}

	type pair struct{ w, v int }
	bigKnapsack2 := func(items []pair, size int) (ans int) {
		n := len(items)
		if n == 1 {
			if items[0].w > size {
				return
			}
			return items[0].v
		}

		sumW, sumV, ps, end := 0, 0, []pair{}, n/2
		var f func(int)
		f = func(p int) {
			if p == end {
				ps = append(ps, pair{sumW, sumV})
				return
			}
			f(p + 1)
			it := items[p]
			sumW += it.w
			sumV += it.v
			f(p + 1)
			sumV -= it.v
			sumW -= it.w
		}
		f(0)

		// 去重，确保重量越大，价值严格越大
		l := ps
		nl := 1
		for i := 1; i < len(l); i++ {
			if l[nl-1].v < l[i].v {
				l[nl] = l[i]
				nl++
			}
		}
		l = l[:nl]

		ps, end = nil, n
		f(n / 2)
		for _, p := range ps {
			// <= size-p.w 的第一个数（因为 l[0].w==0 所以 i 一定非负）
			i := sort.Search(len(l), func(i int) bool { return l[i].w+p.w > size }) - 1
			if l[i].v+p.v > ans {
				ans = l[i].v + p.v
			}
		}
		return
	}

	// 剪枝:
	// todo https://blog.csdn.net/weixin_43914593/article/details/104613920 算法竞赛专题解析（7）：搜索进阶(2)--剪枝

	// A*:
	// todo https://blog.csdn.net/weixin_43914593/article/details/104935011 算法竞赛专题解析（9）：搜索进阶(4)--A*搜索
	//  https://www.redblobgames.com/pathfinding/a-star/introduction.html

	// 舞蹈链 Dancing Links 精确覆盖问题
	// https://en.wikipedia.org/wiki/Dancing_Links
	// TODO: https://oi-wiki.org/search/dlx/
	//       https://leverimmy.blog.luogu.org/dlx-xiang-xi-jiang-jie
	//       https://www.luogu.com.cn/blog/Parabola/qian-tan-shen-xian-suan-fa-dlx
	//       https://www.cnblogs.com/grenet/p/3145800.html
	//       https://www.cnblogs.com/grenet/p/3163550.html
	//   https://lsr2002.blog.luogu.org/wu-dao-lian
	// 模板题+讲解
	//       todo http://hihocoder.com/contest/hiho101/problem/1
	//       http://hihocoder.com/contest/hiho102/problem/1
	//       https://www.luogu.com.cn/problem/P4929

	// 对抗搜索与 Alpha-Beta 剪枝
	// https://www.luogu.com.cn/blog/pks-LOVING/zhun-bei-tou-ri-bao-di-fou-qi-yan-di-blog

	_ = []interface{}{
		loopAny, chooseAny, chooseAtMost, searchCombinations, searchPermutations,
		genSubStrings,
		iterWithLimits, iterWithLimitsAndSum,
		combinations, combinationsWithRepetition,
		permutations, permuteAll, nextPermutation, rankPermutation, kthPermutation,
		bigKnapsack, bigKnapsack2,
	}
}

/* 枚举
枚举所有 2^n 子集
枚举子集的所有子集
枚举大小为 k 的子集
枚举格点周围（曼哈顿距离、切比雪夫距离）
*/
func _(abs func(int) int) {
	// 枚举 {0,1,...,n-1} 的全部子集
	loopSet := func(a []int) {
		n := len(a)
		f := func(sub int) (res int) {
			for i, v := range a {
				if sub>>i&1 == 1 {
					// do(v)...
					_ = v

				}
			}
			return
		}
		for sub := 0; sub < 1<<n; sub++ {
			f(sub)
		}
	}

	// 枚举 set 的全部子集
	// 作为结束条件，处理完 0 之后，会有 -1&set == set
	//
	// 你可能会好奇，为什么 sub = (sub - 1) & set 这样写一定可以「跳到」下一个子集呢？会不会漏呢？
	// 正确性理由见 https://leetcode.cn/circle/discuss/CaOJ45/
	loopSubset := func(n, set int) {
		// 所有子集
		for sub, ok := set, true; ok; ok = sub != set {
			// do(sub)...

			sub = (sub - 1) & set
		}

		// 所有子集（写法二）
		for sub := set; ; sub = (sub - 1) & set {
			// do(sub)...

			if sub == 0 {
				break
			}
		}

		// 非空子集
		for sub := set; sub > 0; sub = (sub - 1) & set {
			// do(sub)...

		}

		// 真子集
		for sub := (set - 1) & set; sub != set; sub = (sub - 1) & set {
			// do(sub)...

		}

		// 非空真子集
		for sub := (set - 1) & set; sub > 0; sub = (sub - 1) & set {
			// do(sub)...

		}

		{
			// EXTRA: 求多个集合（状压）的所有非空子集组成的集合
			// https://ac.nowcoder.com/acm/contest/7607/B
			has := [1e6 + 1]bool{0: true}
			var f func(uint)
			f = func(v uint) {
				if has[v] {
					return
				}
				has[v] = true
				for w := v; w > 0; w &= w - 1 {
					f(v ^ w&-w)
				}
			}
			//for _, v := range a {
			//	f(v)
			//}
		}
	}

	// 枚举 set 的全部超集（父集）ss
	loopSuperset := func(n, set int) {
		for ss := set; ss < 1<<n; ss = (ss + 1) | set {
			// do(ss)...

		}
	}

	// Gosper's Hack：枚举大小为 n 的集合的大小为 k 的子集（按字典序）
	// 我的视频讲解 https://www.bilibili.com/video/BV1na41137jv?t=15m43s
	// https://en.wikipedia.org/wiki/Combinatorial_number_system#Applications
	// 比如在 n 个数中求满足某种性质的最大子集，则可以从 n 开始倒着枚举子集大小，直到找到一个符合性质的子集
	// 例题（TS1）GCJ 2018 R2 Costume Change https://codingcompetitions.withgoogle.com/codejam/round/0000000000007706/0000000000045875
	// LC2397 https://leetcode.cn/problems/maximum-rows-covered-by-columns/
	// https://leetcode.cn/problems/closed-number-lcci/
	loopSubsetK := func(a []int, k int) {
		n := len(a)
		for sub := 1<<k - 1; sub < 1<<n; {
			// do(a, sub) ...
			lb := sub & -sub
			x := sub + lb
			// 下式等价于 sub = (sub^x)/lb>>2 | x
			// 把除法改成右移 bits.TrailingZeros 可以快好几倍
			sub = (sub^x)>>bits.TrailingZeros(uint(lb))>>2 | x
		}
	}

	// 枚举各个 1 位的另一种方法
	// 每次统计尾 0 的个数，然后移除最右侧的 1
	// benchmark 了一下，效率比一个个位上去检查是否为 1 要快
	{
		var mask uint
		for ; mask > 0; mask &= mask - 1 {
			p := bits.TrailingZeros(mask)
			_ = p
		}
	}

	//

	// 获取螺旋遍历的所有坐标         螺旋矩阵 Spiral Matrix
	// LC54 https://leetcode.cn/problems/spiral-matrix/
	// LC59 https://leetcode.cn/problems/spiral-matrix-ii/
	// LC885 https://leetcode.cn/problems/spiral-matrix-iii/
	// LC2326 https://leetcode.cn/problems/spiral-matrix-iv/
	// https://ac.nowcoder.com/acm/contest/6489/C
	type pair struct{ x, y int }
	loopSpiralMatrix := func(n, m int) []pair { // n 行 m 列
		dir4 := []struct{ x, y int }{{0, 1}, {1, 0}, {0, -1}, {-1, 0}} // 右下左上
		mat := make([][]int, n)
		for i := range mat {
			mat[i] = make([]int, m)
			for j := range mat[i] {
				mat[i][j] = -1
			}
		}
		pos := make([]pair, n*m)
		i, j, di := 0, 0, 0
		for id := 0; id < n*m; id++ {
			pos[id] = pair{i, j}
			mat[i][j] = id
			d := dir4[di]
			if x, y := i+d.x, j+d.y; x < 0 || x >= n || y < 0 || y >= m || mat[x][y] != -1 {
				di = (di + 1) % 4
				d = dir4[di]
			}
			i += d.x
			j += d.y
		}
		return pos
	}

	// 顺时针遍历矩阵从外向内的第 d 圈（保证不自交）
	// LC1914 https://leetcode.cn/problems/cyclically-rotating-a-grid/
	loopAround := func(a [][]int, d int) []int {
		n, m := len(a), len(a[0])
		b := make([]int, 0, (n+m-d*4-2)*2)
		for j := d; j < m-d; j++ { // →
			b = append(b, a[d][j])
		}
		for i := d + 1; i < n-d; i++ { // ↓
			b = append(b, a[i][m-1-d])
		}
		for j := m - d - 2; j >= d; j-- { // ←
			b = append(b, a[n-1-d][j])
		}
		for i := n - d - 2; i > d; i-- { // ↑
			b = append(b, a[i][d])
		}
		return b
	}

	// 获取之字遍历的所有坐标
	loopZigZag := func(n, m int) []pair { // n 行 m 列
		pos := make([]pair, 0, n*m)
		for i := 0; i < n; i++ {
			for j := 0; j < m; j++ {
				pos = append(pos, pair{i, j})
			}
			i++
			if i == n {
				break
			}
			for j := m - 1; j >= 0; j-- {
				pos = append(pos, pair{i, j})
			}
		}
		return pos
	}

	/*
		遍历以 (ox, oy) 为中心的曼哈顿距离为 dis 的【边界】上的格点
		例如 dis=2 时：
		  #
		 # #
		# @ #
		 # #
		  #
	*/
	dir4r := []struct{ x, y int }{{-1, 1}, {-1, -1}, {1, -1}, {1, 1}} // 逆时针
	loopAroundManhattan := func(n, m, ox, oy, dis int, f func(x, y int)) {
		if dis == 0 {
			f(ox, oy)
			return
		}
		x, y := ox+dis, oy // 从最右顶点出发，逆时针移动
		for _, d := range dir4r {
			for k := 0; k < dis; k++ {
				if 0 <= x && x < n && 0 <= y && y < m {
					f(x, y)
				}
				x += d.x
				y += d.y
			}
		}
	}

	{
		// 从上到下，遍历以 (ox, oy) 为中心的曼哈顿距离 <= dis 的【所有】格点
		var n, m, ox, oy, dis int
		for i := max(ox-dis, 0); i <= ox+dis && i < n; i++ {
			d := dis - abs(ox-i)
			for j := max(oy-d, 0); j <= oy+d && j < m; j++ {
				if i == ox && j == oy {
					continue
				}
				// f(i, j)

			}
		}
	}

	// 曼哈顿圈序遍历
	// LC1030 https://leetcode.cn/problems/matrix-cells-in-distance-order/
	loopAllManhattan := func(n, m, ox, oy int, f func(x, y int)) {
		f(ox, oy)
		maxDist := max(ox, n-1-ox) + max(oy, m-1-oy)
		for dis := 1; dis <= maxDist; dis++ {
			x, y := ox+dis, oy // 从最右顶点出发，逆时针移动
			for _, d := range dir4r {
				for k := 0; k < dis; k++ {
					if 0 <= x && x < n && 0 <= y && y < m {
						f(x, y)
					}
					x += d.x
					y += d.y
				}
			}
		}
	}

	/*
		遍历以 (ox, oy) 为中心的切比雪夫距离为 dis 的【边界】上的格点
		#####
		#   #
		# @ #
		#   #
		#####
	*/
	loopAroundChebyshev := func(n, m, ox, oy, dis int) {
		// 上下
		for _, x := range []int{ox - dis, ox + dis} {
			if 0 <= x && x < n {
				for y := max(oy-dis, 0); y <= min(oy+dis, m-1); y++ {
					// do ...
				}
			}
		}
		// 左右（注意四角已经被上面的循环枚举到了）
		for _, y := range []int{oy - dis, oy + dis} {
			if 0 <= y && y < m {
				for x := max(ox-dis, 0) + 1; x <= min(ox+dis, n-1)-1; x++ {
					// do ...
				}
			}
		}
	}

	// 第一排在右上，最后一排在左下
	// 每排从左上到右下
	// LC2711 https://leetcode.cn/problems/difference-of-number-of-distinct-values-on-diagonals/
	// - [1329. 将矩阵按对角线排序](https://leetcode.cn/problems/sort-the-matrix-diagonally/) 1548
	// - [562. 矩阵中最长的连续1线段](https://leetcode.cn/problems/longest-line-of-consecutive-one-in-matrix/)（会员题）
	loopDiagonal := func(n, m int) {
		for s := 1; s < n+m; s++ {
			minJ := max(0, m-s)
			maxJ := min(m-1, n+m-1-s)
			for j := minJ; j <= maxJ; j++ {
				i := s + j - m
				_ = i

			}
		}
	}

	// 第一排在左上，最后一排在右下
	// 每排从左下到右上
	// LC498 https://leetcode.cn/problems/diagonal-traverse/
	// - [562. 矩阵中最长的连续1线段](https://leetcode.cn/problems/longest-line-of-consecutive-one-in-matrix/)（会员题）
	loopAntiDiagonal := func(n, m int) {
		for s := 0; s < n+m-1; s++ {
			minJ := max(0, s-n+1)
			maxJ := min(m-1, s)
			for j := minJ; j <= maxJ; j++ {
				i := s - j
				_ = i

			}
		}
	}

	// 以主对角线为第一列（行），然后向右（下）平移遍历
	// 例如
	// 0 3 6 9
	// 10 1 4 7
	// 8 11 2 5
	// https://codeforces.com/problemset/problem/1276/C
	circleLoopDiagonal := func(n, m int) {
		if n <= m {
			// 向右平移
			for rc := 0; rc < n*m; rc++ {
				_c, _r := rc/n, rc%n
				i, j := _r, (_c+_r)%m
				_, _ = i, j

			}
		} else {
			// 向下平移
			for rc := 0; rc < n*m; rc++ {
				_r, _c := rc/m, rc%m
				i, j := (_r+_c)%n, _c
				_, _ = i, j

			}
		}
	}

	// 保证边界在范围内且 x0 <= x1 且 y0 <= y1
	loopBorder := func(x0, y0, x1, y1 int) {
		if y0 == y1 {
			for i := x0; i <= x1; i++ {
				// do(i, y0) ...

			}
			return
		}
		for i := x0; i <= x1; i++ {
			for j := y0; j <= y1; {
				// do(i, j) ...

				if i == x0 || i == x1 {
					j++
				} else {
					j += y1 - y0
				}
			}
		}
	}

	_ = []interface{}{
		loopSet, loopSubset, loopSuperset, loopSubsetK,
		loopSpiralMatrix, loopAround, loopZigZag,
		loopAroundManhattan, loopAllManhattan, loopAroundChebyshev,
		loopDiagonal, loopAntiDiagonal, circleLoopDiagonal,
		loopBorder,
	}
}

/*
网格/矩阵上的搜索
NOTE: 对于 n*m 的网格图，BFS 最多只占用 O(min(n,m)) 的空间，而 DFS 最多会占用 O(nm) 的空间

## 题单（右边数字为难度分）

#### 网格图 DFS
- [200. 岛屿数量](https://leetcode.cn/problems/number-of-islands/)
- [695. 岛屿的最大面积](https://leetcode.cn/problems/max-area-of-island/)
- [面试题 16.19. 水域大小](https://leetcode.cn/problems/pond-sizes-lcci/)
- [463. 岛屿的周长](https://leetcode.cn/problems/island-perimeter/)
- [2658. 网格图中鱼的最大数目](https://leetcode.cn/problems/maximum-number-of-fish-in-a-grid/) 1490
- [1034. 边界着色](https://leetcode.cn/problems/coloring-a-border/) 1579
- [1020. 飞地的数量](https://leetcode.cn/problems/number-of-enclaves/) 1615
- [2684. 矩阵中移动的最大次数](https://leetcode.cn/problems/maximum-number-of-moves-in-a-grid/) 1626
- [1254. 统计封闭岛屿的数目](https://leetcode.cn/problems/number-of-closed-islands/) 1659
- [130. 被围绕的区域](https://leetcode.cn/problems/surrounded-regions/)
- [1391. 检查网格中是否存在有效路径](https://leetcode.cn/problems/check-if-there-is-a-valid-path-in-a-grid/) 1746
- [417. 太平洋大西洋水流问题](https://leetcode.cn/problems/pacific-atlantic-water-flow/)
   - https://codeforces.com/problemset/problem/1651/D 1900
- [529. 扫雷游戏](https://leetcode.cn/problems/minesweeper/)
- [1559. 二维网格图中探测环](https://leetcode.cn/problems/detect-cycles-in-2d-grid/) 1838
- [827. 最大人工岛](https://leetcode.cn/problems/making-a-large-island/) 1934
   - https://codeforces.com/contest/616/problem/C 1600
   - 可以改一排或一列 https://codeforces.com/problemset/problem/1985/H1
   - 可以改一排和一列 https://codeforces.com/problemset/problem/1985/H2
https://codeforces.com/problemset/problem/1948/C 1300
https://codeforces.com/problemset/problem/723/D 1600
https://codeforces.com/problemset/problem/598/D 1700
https://codeforces.com/problemset/problem/1365/D 1700

#### 网格图 BFS
- [542. 01 矩阵](https://leetcode.cn/problems/01-matrix/) *多源 BFS
- [994. 腐烂的橘子](https://leetcode.cn/problems/rotting-oranges/) 1433
- [2684. 矩阵中移动的最大次数](https://leetcode.cn/problems/maximum-number-of-moves-in-a-grid/) 1626
- [1926. 迷宫中离入口最近的出口](https://leetcode.cn/problems/nearest-exit-from-entrance-in-maze/) 1638
- [1091. 二进制矩阵中的最短路径](https://leetcode.cn/problems/shortest-path-in-binary-matrix/) 1658
- [1162. 地图分析](https://leetcode.cn/problems/as-far-from-land-as-possible/) 1666
- [1824. 最少侧跳次数](https://leetcode.cn/problems/minimum-sideway-jumps/) 1778 0-1 BFS
- [934. 最短的桥](https://leetcode.cn/problems/shortest-bridge/) 1826
- [2146. 价格范围内最高排名的 K 样物品](https://leetcode.cn/problems/k-highest-ranked-items-within-a-price-range/) 1837
- [1293. 网格中的最短路径](https://leetcode.cn/problems/shortest-path-in-a-grid-with-obstacles-elimination/) 1967
- [1210. 穿过迷宫的最少移动次数](https://leetcode.cn/problems/minimum-moves-to-reach-target-with-rotations/) 2022
- [1368. 使网格图至少有一条有效路径的最小代价](https://leetcode.cn/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/) 2069 0-1 BFS
- [490. 迷宫](https://leetcode.cn/problems/the-maze/)（会员题）
- [505. 迷宫 II](https://leetcode.cn/problems/the-maze-ii/)（会员题）
- [499. 迷宫 III](https://leetcode.cn/problems/the-maze-iii/)（会员题）
- [317. 离建筑物最近的距离](https://leetcode.cn/problems/shortest-distance-from-all-buildings/)（会员题）
https://codeforces.com/problemset/problem/329/B 1500
https://codeforces.com/problemset/problem/1955/H 2300
https://codeforces.com/problemset/problem/1301/F 2600 BFS 进阶玩法
- 同色入队 - 往四周走 - 同色跳跃 - 往四周走 - 同色跳跃 - ...
- 记录访问过的颜色
https://atcoder.jp/contests/abc317/tasks/abc317_e
另见 graph.go 中的 0-1 BFS

#### 综合
- [1631. 最小体力消耗路径](https://leetcode.cn/problems/path-with-minimum-effort/) 1948
- [778. 水位上升的泳池中游泳](https://leetcode.cn/problems/swim-in-rising-water/) 2097
- [329. 矩阵中的最长递增路径](https://leetcode.cn/problems/longest-increasing-path-in-a-matrix/)
- [1036. 逃离大迷宫](https://leetcode.cn/problems/escape-a-large-maze/) 2165
- [864. 获取所有钥匙的最短路径](https://leetcode.cn/problems/shortest-path-to-get-all-keys/) 2259
- [1263. 推箱子](https://leetcode.cn/problems/minimum-moves-to-move-a-box-to-their-target-location/) 2297
- [2258. 逃离火灾](https://leetcode.cn/problems/escape-the-spreading-fire/) 2347
   - https://www.luogu.com.cn/problem/UVA11624
- [2556. 二进制矩阵中翻转最多一次使路径不连通](https://leetcode.cn/problems/disconnect-path-in-a-binary-matrix-by-at-most-one-flip/) 2369
- [2577. 在网格图中访问一个格子的最少时间](https://leetcode.cn/problems/minimum-time-to-visit-a-cell-in-a-grid/) 2382
- [2617. 网格图中最少访问的格子数](https://leetcode.cn/problems/minimum-number-of-visited-cells-in-a-grid/) 2582
- [LCP 13. 寻宝](https://leetcode.cn/problems/xun-bao/)
- [LCP 31. 变换的迷宫](https://leetcode.cn/problems/Db3wC1/)
- [LCP 45. 自行车炫技赛场](https://leetcode.cn/problems/kplEvH/)
- [LCP 75. 传送卷轴](https://leetcode.cn/problems/rdmXM7/)
- [1728. 猫和老鼠 II](https://leetcode.cn/problems/cat-and-mouse-ii/) 2849
- [1102. 得分最高的路径](https://leetcode.cn/problems/path-with-maximum-minimum-value/)（会员题）
易错题 https://codeforces.com/problemset/problem/540/C 2000

#### 其它
- [54. 螺旋矩阵](https://leetcode.cn/problems/spiral-matrix/)
- [59. 螺旋矩阵 II](https://leetcode.cn/problems/spiral-matrix-ii/)

*/
func gridCollection() {
	type pair struct{ x, y int }
	dir4 := []pair{{-1, 0}, {1, 0}, {0, -1}, {0, 1}} // 上下左右

	// 获取网格图的 labelS, labelT 的坐标
	getST := func(g [][]byte, labelS, labelT byte) (pair, pair) {
		var s, t pair
		for i, row := range g {
			for j, b := range row {
				p := pair{i, j}
				if b == labelS {
					s = p
				} else if b == labelT {
					t = p
				}
			}
		}
		return s, t
	}

	// 矩形网格图，返回从起点 (s.x,s.y) 到其余所有可达点的最短距离。'#' 表示无法通过的格子   bfsGridAll 单源最短距离
	// https://codeforces.com/contest/1520/problem/G
	// LC2146 https://leetcode.cn/problems/k-highest-ranked-items-within-a-price-range/
	disAll := func(g [][]byte, sx, sy int) [][]int {
		n, m := len(g), len(g[0])
		dis := make([][]int, n)
		for i := range dis {
			dis[i] = make([]int, m)
			for j := range dis[i] {
				dis[i][j] = -1
			}
		}
		dis[sx][sy] = 0
		q := []pair{{sx, sy}}
		for step := 1; len(q) > 0; step++ {
			tmp := q
			q = nil
			for _, p := range tmp {
				for _, d := range dir4 {
					if x, y := p.x+d.x, p.y+d.y; 0 <= x && x < n && 0 <= y && y < m && g[x][y] != '#' && dis[x][y] < 0 { //
						dis[x][y] = step
						q = append(q, pair{x, y})
					}
				}
			}
		}
		return dis
	}

	// 矩形网格图，返回从起点 (s.x,s.y) 到目标 (t.x,t.y) 的最短距离。'#' 表示无法通过的格子   bfsGridDep 最短距离
	// 无法到达时返回 inf
	// t 也可是别的东西，比如某个特殊符号等
	// https://ac.nowcoder.com/acm/contest/6781/B
	// https://atcoder.jp/contests/abc184/tasks/abc184_e
	disST := func(g [][]byte, sx, sy, tx, ty int) int {
		n, m := len(g), len(g[0])
		const inf int = 1e9 // 1e18

		vis := make([][]bool, n)
		for i := range vis {
			vis[i] = make([]bool, m)
		}
		vis[sx][sy] = true
		q := []pair{{sx, sy}}
		for step := 0; len(q) > 0; step++ {
			tmp := q
			q = nil
			for _, p := range tmp {
				// g[p.x][p.y] == 'T'
				if p.x == tx && p.y == ty {
					return step
				}
				for _, d := range dir4 {
					if xx, yy := p.x+d.x, p.y+d.y; 0 <= xx && xx < n && 0 <= yy && yy < m && !vis[xx][yy] && g[xx][yy] != '#' { //
						//if p.x == tx && p.y == ty {
						//	return step
						//}
						vis[xx][yy] = true
						q = append(q, pair{xx, yy})
					}
				}
			}
		}
		return inf
	}

	// 从 s 出发寻找 t，返回所有 t 所处的坐标。'#' 表示无法通过的格子   bfsGrid 可达
	// https://leetcode.cn/contest/season/2020-spring/problems/xun-bao/
	findAllReachableTargets := func(g [][]byte, s pair, t byte) (ps []pair) {
		n, m := len(g), len(g[0])
		vis := make([][]bool, n)
		for i := range vis {
			vis[i] = make([]bool, m)
		}
		vis[s.x][s.y] = true
		q := []pair{s}
		for len(q) > 0 {
			p := q[0]
			q = q[1:]
			x, y := p.x, p.y
			if g[x][y] == t { // x == n-1 && y == m-1
				ps = append(ps, p)
			}
			for _, d := range dir4 {
				if xx, yy := x+d.x, y+d.y; 0 <= xx && xx < n && 0 <= yy && yy < m && !vis[xx][yy] && g[xx][yy] != '#' { //
					vis[xx][yy] = true
					q = append(q, pair{xx, yy})
				}
			}
		}
		return
	}

	// DFS 格点找有多少个连通分量   dfsGrid
	cntCC := func(g [][]byte) (cnt int) {
		n, m := len(g), len(g[0])
		vis := make([][]bool, n)
		for i := range vis {
			vis[i] = make([]bool, m)
		}
		const valid byte = '.'
		var f func(int, int)
		f = func(x, y int) {
			if x < 0 || x >= n || y < 0 || y >= m || vis[x][y] || g[x][y] != valid {
				return
			}
			vis[x][y] = true
			for _, d := range dir4 {
				f(x+d.x, y+d.y)
			}
		}
		for i, row := range g {
			for j, v := range row {
				if v != valid && !vis[i][j] {
					continue
				}
				cnt++
				f(i, j)
			}
		}
		return
	}

	// 下列代码来自 LC1254 https://leetcode.cn/problems/number-of-closed-islands/
	// NOTE: 对于搜索格子的题，可以不用创建 vis 而是通过修改格子的值为范围外的值（如零、负数、'#' 等）来做到这一点  dfsGrid
	dfsValidGrids := func(g [][]byte) (comps [][]pair) {
		n, m := len(g), len(g[0])
		vis := make([][]bool, n)
		for i := range vis {
			vis[i] = make([]bool, m)
		}
		const validCell byte = '.'
		var comp []pair
		var f func(int, int) bool
		f = func(i, j int) bool {
			if i < 0 || i >= n || j < 0 || j >= m {
				return false
			}
			if vis[i][j] || g[i][j] != validCell {
				return true
			}
			vis[i][j] = true
			comp = append(comp, pair{i, j})
			validCC := true
			for _, d := range dir4 {
				x, y := i+d.x, j+d.y
				if !f(x, y) {
					validCC = false // 遍历完该连通分量再 return，保证不重不漏
				}
			}
			return validCC
		}
		for i, row := range g {
			for j, v := range row {
				if v != validCell && !vis[i][j] {
					continue
				}
				comp = []pair{}
				if f(i, j) {
					comps = append(comps, comp)
					// do comp ...
				}
			}
		}
		return
	}

	// 周赛 212D https://leetcode.cn/problems/rank-transform-of-a-matrix/
	findSameValueCC := func(mat [][]int) {
		type pair struct{ x, y int }
		type vPos struct {
			v   int
			pos []pair
		}
		allPos := map[int][]pair{}
		for i, row := range mat {
			for j, v := range row {
				allPos[v] = append(allPos[v], pair{i, j})
			}
		}
		vps := []vPos{}
		for v, pos := range allPos {
			np := len(pos)
			g := make([][]int, np)
			for i := 1; i < np; i++ {
				if pos[i].x == pos[i-1].x {
					g[i] = append(g[i], i-1)
					g[i-1] = append(g[i-1], i)
				}
			}
			pid := map[pair]int{}
			col := map[int][]int{} // 按列分组的横坐标
			for i, p := range pos {
				pid[p] = i
				col[p.y] = append(col[p.y], p.x)
			}
			for j, xs := range col {
				for k := 1; k < len(xs); k++ {
					i := pid[pair{xs[k-1], j}]
					i2 := pid[pair{xs[k], j}]
					g[i] = append(g[i], i2)
					g[i2] = append(g[i2], i)
				}
			}
			// 寻找值相同且同行列的所有位置
			var cc []pair
			vis := make([]bool, np)
			var f func(int)
			f = func(v int) {
				vis[v] = true
				cc = append(cc, pos[v])
				for _, w := range g[v] {
					if !vis[w] {
						f(w)
					}
				}
				return
			}
			for i, b := range vis {
				if !b {
					cc = nil
					f(i)
					vps = append(vps, vPos{v, cc})
				}
			}
		}
		sort.Slice(vps, func(i, j int) bool { return vps[i].v < vps[j].v })
		//for _, vp := range vps {
		//	v, pos := vp.v, vp.pos
		//
		//}
	}

	// other help functions

	isValidPoint := func(g [][]byte, p pair) bool {
		n, m := len(g), len(g[0])
		return 0 <= p.x && p.x < n && 0 <= p.y && p.y < m && g[p.x][p.y] != '#'
	}

	findOneTargetAnyWhere := func(g [][]byte, tar byte) pair {
		for i, row := range g {
			for j, b := range row {
				if b == tar {
					return pair{i, j}
				}
			}
		}
		return pair{-1, -1}
	}

	findAllTargetsAnyWhere := func(g [][]byte, tar byte) (ps []pair) {
		for i, row := range g {
			for j, b := range row {
				if b == tar {
					ps = append(ps, pair{i, j})
				}
			}
		}
		return
	}

	_ = []interface{}{
		getST,
		disAll, disST, findAllReachableTargets,
		cntCC, dfsValidGrids,
		findSameValueCC,
		isValidPoint, findOneTargetAnyWhere, findAllTargetsAnyWhere,
	}
}