主要考察点就是回溯
for (i := 1; i<=n;i++)
这个表示开始搜每个点 (1,2,3,…开头的,换句话就是首字母是i=1,2,3等的)
dfs(u+1) 表示深搜下一个点(第二个点,第三个点等等)
而每次搜的时候赋上值,path[u]=i,并标记搜过了st[u]=true.
当所有的位数都搜过时,回溯。(根据题意也就三位数填满后。)
之所以回溯是因为对于下个点它是没搜过的,所以要把上次的标记清干净。
比如:
1 2 3 此时path[1]=true, path[2]= true, path[3]=true然后触发u==3返回,也就是结束此臂的深搜.
这时,第三个点搜完了,需要继续搜第二个点。所以12_的path[3]=false置为未搜。
第二位填2 搜过了,轮到第二位填3了,所以path[2]=false置为未搜然后进入第二位填3的循环
1 3 _ 此时1,3填过了path[1,3]是true. 所以只能填1 3 2
至此,第一位填1搜完了
继续回溯到第一位填2, …以此类推
2 1 , 2 3 ,
…
package main
import("fmt")
const N = 8
var n int
var st [N]bool
var path [N]int
func dfs(u int){
if (u == n){
for i := 0; i < n; i++{
fmt.Printf("%d ", path[i])
}
fmt.Println("")
return
} else {
for i := 1;i <= n;i++{
if (st[i] == false){
path[u] = i
st[i] = true
dfs(u+1)
st[i]= false
}
}
}
}
func main(){
fmt.Scanln(&n)
//fmt.Printf("%d",n)
dfs(0)
}