DFS 深搜专题 入门典例 -- 凌宸1642

深度优先搜索 是一种 枚举所有完整路径以遍历所有情况的搜索方法 ，使用 递归 可以很好的实现 深度优先搜索。

1 最大价值

题目描述

​ 有 n 件物品，每件物品的重量为 w[i] , 价值为 c[i] 。现在需要选出若干件物品放入一个容器为 V 的背包中，使得在选入背包的物品重量和不超过容量 V 的前提下 ，让背包中的物品的价值之和最大，求最大价值。(1 ≤ n≤ 20 )

输入描述：

​ 第一行输入物品总数 n 和 背包容量 v 。

​ 第二行输入 n 个整数， 分别表示 n 件物品各自的重量。

​ 第三行输入 n 个整数， 分别表示 n 件物品各自的价值。

输出描述：

​ 对于每个测试用例，在一行中输出最大价值。

样例输入：

5 8
3 5 1 2 2
4 5 2 1 3

样例输出：

10

#include<bits/stdc++.h>
using namespace std ;
#define MAX 30
int n , v , maxValue = 0 ; // 物品件数 n，背包容量 v,最大价值 maxValue 
int w[MAX] , c[MAX] ; // w[i]为每件物品的重量， c[i]每件物品的价值
// dfs ，index 表示当前处理物品的编号 ， sumW sumC 分别为当前 总重量 和 总价值
void dfs(int index , int sumW , int sumC){
	if(index == n) { // 已经完成对 n 件物品的处理
		if(sumW <= v && sumC > maxValue ) maxValue = sumC ; // 如果此时最大价值符合题意，则更新
		return ;
	}
	// 岔道口 
	dfs(index + 1 , sumW , sumC) ; // 不选择第 index 件物品
	dfs(index + 1 , sumW + w[index] , sumC + c[index]) ; // 选择了第 index 件物品 
} 
int main(){
	cin >> n >> v ; // 输入 物品数 n 和 背包容量 v 
	for(int i = 0 ; i < n ; i ++) cin >> w[i] ; // 输入 n 件物品的 重量
	for(int i = 0 ; i < n ; i ++) cin >> c[i] ; // 输入 n 件物品的 价值
	dfs(0 , 0 , 0) ; // 调用 dfs 进行深搜
	cout << maxValue << endl ;  // 深搜结束后， maxValue 中存有最大价值，直接输出
	return 0;
}
// 对此 dfs 进行剪枝后 ，剪枝是在保证算法正确的情况下，通过题目条件限制来减少 DFS 计算量的方法
void dfs(int index , int sumW , int sumC){
    if(index == n) return ; //完成对 n 件物品的选择
    dfs(index + 1 , sumW , sumC) ; // 未选择第 index 件物品
    if(sumW + w[index] <= v ) { // 只有当选择第 index 件物品之后，容量不会超过 v ，才进行选择
        if(sumC + c[index] > maxValue)
            maxValue = sumC + c[index] ;  // 更新最大价值 maxValue
        dfs(index + 1 , sumW + w[index] , sumC + c[index]) ; // 选择第 index 件物品
	}
}

2 最优方案

题目描述：

​ 给定一个序列，枚举这个序列的所有子序列(可以不连续)。例如对序列{1,2,3}来说，他的所有子序列为{1}，{2}，{3}，{1,2}，{1,3}，{1,2,3}。枚举所有子序列的目的很明显——可以从中选择一个“最优”子序列，使它的某个特征是所有子序列中最优的；如果有需要，还可以将这个最优子序列保存下来。显然，这个问题也可以等价于 枚举从 N 个整数中选择 K 个数的所有方案。

​ 给定 N 个整数（可能有负数），从中选择 K 个数，使得这 K 个数的和恰好等于给定的一个整数 X ； 如果有多种方案，则选择他们当中平方和最大的一个。数据保证这样的方案唯一。例如，从 4 个整数{2,3,3,4}中选择两个数，使他们的和为 6 。显然有两种方案{2,4} 和{3,3} ，其中平方和最大的方案为{2,4}。

输入描述：

​ 第一行输入 3 个正整数 ，依次输入序列的长度 N，从中选择数的数量 K ，和恰好等于的和 X 。

​ 第二行输入 N 个整数（可能有负数），表示序列中的数。

输出描述：

​ 输出分两行，第一行输出 K 个数 , 表示最优序列中的元素。元素之间用空格分隔，且行末没有于的空格

​ 第二行输出 最优方案的平方和。

样例输入：

4 2 6
2 3 3 4

样例输出：

2 4
20

#include<bits/stdc++.h>
using namespace std ;
#define MAX 100010
int n , k , x , maxSumSqu = - 1 , a[MAX] ;//分别表示，序列长度，选择数量，恰好的和，最大平方和，序列
vector<int> temp , ans ;  // temp 存放临时方案，ans 存放平方和最大的方案 
// dfs参数列表分别表示 处理第 index 个数，现在已选 nowK 个数，当前已选数字的和 sum 及其平方和 sumSqu
void dfs(int index , int nowK , int sum , int sumSqu){
	// 找到第 k 个数的和为 x 
	if(nowK == k && sum == x){
		if(sumSqu > maxSumSqu){ // 如果比当前的更优 
			maxSumSqu = sumSqu ; // 更新最大平方和 
			ans = temp ; // 更新最优方案 
		}
		return ;
	}
	// 已经处理完 n 个数，或者超过 k 个数，或者和超过 x，返回 
	if(index == n || nowK > k || sum > x) return ; 
	// 选第 index 个数
	temp.push_back(a[index]) ;// 将第 index 个数 入栈，然候搜索下一个数，注意参数各个值的变化
	dfs(index + 1 , nowK + 1 , sum + a[index] , sumSqu + a[index] * a[index]) ;
	// 不选第 index 个数
	temp.pop_back() ; // 先将第 index 个数 出栈( 还原现场 )  
	dfs(index + 1 , nowK , sum , sumSqu) ; // 继续搜索下一个数
}
int main(){
    //cin >> n >> k >> x ; 
	scanf("%d%d%d" , &n , &k , &x) ;// 依次输入序列的长度 n ， 选择数的数量 k ，恰好的和 x
	for(int i = 0 ; i < n ; i ++) scanf("%d" , &a[i])  ; // 输入序列
	dfs(0 , 0 , 0 , 0) ; // 调用 dfs 
	for(int i = 0 ; i < ans.size() ; i ++){ // dfs 后 ， ans中存储的是最优子序列，遍历输出
        //cout<< ans[i]<<" " ;
        printf("%d%c" , ans[i] , (i == ans.size() - 1)?'\n':' ') ;
	}
    printf("%d\n" , maxSumSqu) ; // 输出最优子序列的 平方和 
	// cout<<endl<<maxSumSqu<<endl ; 
	return 0 ;
}

3 全排列

题目描述：

​ 排列与组合是常用的数学方法。先给一个正整数 ( 1 < = n < = 10 ) 。例如n＝3，所有组合,并且按字典序输出：

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

输入描述：

​ 在一行中输入正整数 n ( 1 < = n < = 10 ) 。

输出描述：

​ 按字典序输出 n 的全排列。每行输出一个排列，数字间用空格分隔，且行末没有多与的空格

样例输入：

3

样例输出：

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

#include<bits/stdc++.h>
using namespace std ;
#define MAX 20 
bool flag[20] = { false } ; // 是否被访问，初值为 false
int num[20] ; // 存储排列
int n ; 
// dfs 参数 index 表述处理排列的第 index 个数
void dfs(int index){
	if(index == n + 1){ // 如果 index 等于 n + 1 ，表明已经完成了一次排列 ，则当前排列
		 // printf("%d" , num[1]) ; 输出第一个元素
		// for(int i = 2 ; i <= n ; i ++)printf(" %d" ,num[i]); 输出空格和后面 n - 1 个元素
		// printf("\n") ; 当前排列全部输出，换行
        // 上述四条语句，等价于如下语句
        for(int i = 1 ; i <= n ; i ++) printf("%d%c" , num[i] , (i == n)?'\n':' ');
		return ; 
	}
	for(int i = 1 ; i <= n ; i ++){ // n 的全排列，就是将 1 - n 都访问一遍 ， 并存在对应位置
		if(flag[i] == false){ // 如果 i 还未访问 
			num[index] = i ; // 将 i 的值存入 num 数组第 index 位置
			flag[i] = true ; // 将 i 的访问标志置为 true
			dfs(index + 1) ;  // 进行下一个位置的 dfs 搜索
			flag[i] = false ; // 还原现场
		}
	}
}
int main(){
	scanf("%d" , &n) ; // 输入正整数 n 
	dfs(1) ; // 调用 dfs
	return 0;
}

4 组合的输出

题目描述：

​ 排列与组合是常用的数学方法，其中组合就是从 n 个元素中抽出 r 个元素(不分顺序且 r ≤ n)，我们可以简单地将 n 个元素理解为自然数 1，2，…，n ，从中任取 r 个数。 例如 n ＝ 5 ，r ＝ 3 ，所有组合为：

1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5

输入描述：

​ 在一行中输入两个自然数 n ，r ( 1 < n < 21，1 ≤ r ≤ n )。

输出描述：

​ 输出所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，所有的组合也按字典顺序。每行中的元素之间用空格分隔，并且行末没有多余的空格。

样例输入：

5 3

样例输出：

1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5

#include<bits/stdc++.h>
using namespace std ;
int n , r ;
vector<int> temp ; // temp 存储当前已选的数
// index 为当前处理的数的下标， nowR是已经有多少个数 
void dfs(int index , int nowR){
	if(nowR == r){ // 如果已选 k 个数，那么输出当前选择的 k 个数
//		printf("%d" ,temp[0]);
//		for(int i = 1 ; i < r ; i ++) printf(" %d" , temp[i]);
//		printf("\n");
		for(int i = 0 ; i < r ; i ++) printf("%d%c" , temp[i] , (i == r - 1)?'\n':' ');
		return ;
	} 
    // 如果已经处理完 n 个数 或者选择数的数量大于 k
	if(index == n + 1 || nowR > r) return ; 
	// 选第 index 个数
	temp.push_back(index) ; // 将 index 入栈 
	dfs(index + 1 , nowR + 1) ; // 继续 dfs 深搜 注意参数的变化
	// 不选第 index 个数
	temp.pop_back() ; // 先将 index 出栈
	dfs(index + 1 , nowR) ;  // 继续 dfs 深搜 注意参数的变化
}
int main(){
	scanf("%d%d" , &n, &r) ; 
	dfs(1 , 0) ; // 调用 dfs 下标解释为 从 1 开始搜索，当前选择数的数量为 0 
	return 0 ;
}

5 组合+判断素数

题目描述：

​ 已知 n 个整数b1,b2,…,bn。以及一个整数 k（k＜n）。 从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。例如当 n = 4，k＝3，4 个整数分别为 3，7，12，19 时，可得全部的组合与它们的和为：

3＋7＋12=22　　3＋7＋19＝29　　7＋12＋19＝38　　3＋12＋19＝34。

现在，要求你计算出和为素数共有多少种。例如上例，只有一种的和为素数：3＋7＋19＝29。

输入描述：

  第一行两个整数：`n` , `k`  `(1 ≤ n ≤ 20，k < n)` 

​ 第二行 n个整数：x1,x2，… , xn (1 ≤ xi ≤ 5000000)

输出描述：

​ 一个整数（满足条件的方案数）。

样例输入：

4 3
3 7 12 19

样例输出：

1

#include<bits/stdc++.h>
using namespace std ;
int num[22] ; // 存储选择的数
int n , k , ans = 0 ; // ans 用来存储满足要求的方案数的数量
// 判断一个数是否为素数的算法 就不必再赘述了
bool isPrime(int x){
	if(n <= 1 || n == 2) return false ; 
	for(int i = 2 ; i <= sqrt(x) ; i ++){
		if(x % i == 0)
			return false ; 
	}
	return true ;
}
// dfs 参数说明：分别表示 处理第 index 个数，当前已选 nowK 个数 ，当前已选数字的和
void dfs(int index , int nowK ,int sum){
	if(nowK == k){ // 如果已选 k 个数 
		if(isPrime(sum)) // 判断当前 k 个数的和 是否为素数， 
			ans ++ ; // 如果是，则方案数 自增 1
		return ;
	}
    // 已经处理了 n 个数 ， 或者 所选数的数量大于 k ，则返回
	if(index == n + 1 || nowK > k) return ; 
	// 选第 index 个数 ；注意 对应参数变化
	dfs(index + 1 , nowK + 1 , sum + num[index]) ;
	// 不选第 index 个数 ；
	dfs(index + 1 , nowK , sum) ; 
} 
int main(){
	scanf("%d%d" , &n ,&k) ; // 输入 n 和 k
	for(int i = 1 ; i <= n ; i ++) scanf("%d" ,&num[i]) ; // 输入 n 个整数
	dfs(1 , 0 , 0) ; // dfs 调用， 处理第 1 个数 当前所选数的数量为 0 当前所选数字的和为 0
	printf("%d\n" , ans) ; // 输出满足要去的结果数
	return 0;
}

6 N 皇后问题

题目描述：

​ 会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将 8 个皇后放在棋盘上（有 8 * 8 个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。

输入描述：

​ 一个整数 n（ 1 ≤ n ≤ 10 ) 。

输出描述：

​ 每行输出对应一种方案，按字典序输出所有方案。每种方案顺序输出皇后所在的列号，相邻两数之间用空格隔开，行末没有多与的空格。如果一组可行方案都没有，输出 no solute! 。

样例输入：

4

样例输出：

2 4 1 3
3 1 4 2

#include<bits/stdc++.h>
using namespace std ;
int n , temp[12] = { 0 } ,cnt = 0 ;  // temp 用来存储当前摆放皇后的列标 ， cnt 用来记录解的个数
bool p[12] = { false } ; // 列表的访问数组 ， 初值为 false 代表都未被访问
// dfs 参数 index 表示当前处理 第 index 列
void dfs(int index){
	if(index == n + 1){ // 已经处理完 n 列 ， 输出当前 temp 中存储的摆放顺序
		cnt ++ ; 
		//printf("%d" ,temp[1]);
		//for(int i = 2 ; i <= n ; i ++) printf(" %d" , temp[i]);
		//printf("\n");
        for(int i = 1 ; i <= n ; i ++) printf("%d%c" , temp[i] , (i == n)?'\n':' ') ;
		return ;
	}
    // 对于 摆放皇后的位置，遍历第 i 到 n 列
	for(int i = 1 ; i <= n ; i ++){
		if(p[i] == false){ // 如果当前列没有皇后
			bool flag = true ; // 定义标志位，看是否对角线上有皇后
			for(int pre = 1 ; pre < index ; pre ++){ // 遍历已经摆放好的皇后
				// 回溯 
				if(abs(index - pre) == abs(i - temp[pre])){ // 如果在某一对角线有冲突
					flag = false ; // 标志位置为 false ，并跳出循环
					break; 
				}
			}
			if(flag){ // 如果对角线没有冲突
				temp[index] = i ; // 将当前列标复制给 temp 的第 index ，即在当前列放一个皇后
				p[i] = true ; // 并置当前位置的访问位 为true 表示已经访问过
				dfs(index + 1) ; // 继续 dfs ，摆放下一个位置的皇后
				p[i] = false ; // 还原现场
			}
		}
	}
}
int main(){
	scanf("%d" , &n) ; // 输入 n 皇后 的规模 n
	dfs(1) ;  // 从 第 1 列开始 dfs
	if(cnt == 0) printf("no solute!\n") ; // 如果解的数目为 0 即无解，按题目要求输出 no solute!
	return 0;
}

7 出栈序列统计

题目描述：

​ 栈是常用的一种数据结构，有 n 个元素在栈顶端一侧等待进栈，栈顶端另一侧是出栈序列。你已经知道栈的操作有两种：push 和 pop ，前者是将一个元素进栈，后者是将栈顶元素弹出。现在要使用这两种操作，由一个操作序列可以得到一系列的输出序列。请你编程求出对于给定的n，计算并输出由操作数序列 1，2，… ，n，经过一系列操作可能得到的输出序列总数。

输入描述：

​ 一个整数 n (1 ≤ n ≤ 15).

输出描述：

​ 一个整数，即可能输出序列的总数目。

样例输入：

3

样例输出：

5

#include<bits/stdc++.h>
using namespace std ;
int n , cnt = 0 ;
// dfs 参数解析，in 代表栈中有多少个元素 ， out 代表还有多少元素需要入栈
void dfs(int in , int out){
	if(out == 0){ // 如果以及没有需要进栈的元素，那么出栈顺序总数目 + 1
		cnt ++ ; 
		return ;	
	}
	if(in == 0) dfs(in + 1,out - 1) ; // 如果栈中没有元素，则只能进行入栈操作
	else if (out != 0){ // 如果栈中有元素，也存在待入栈的元素
		dfs(in + 1 , out - 1 ) ;	// 进行入栈操作
		dfs(in - 1 , out) ;	// 进行出栈操作
	}
}
int main(){
	scanf("%d" , &n) ; 
	dfs(0 , n) ; // 调用 dfs 初始栈内元素个数为 0 ，需要入栈元素为 n
	printf("%d\n" , cnt) ; // 输出解的个数
	return 0 ;
}

8 走迷宫

题目描述：　

　 有一个n * m格的迷宫(表示有 n 行、m 列)，其中有可走的也有不可走的，如果用 1 表示可以走，0 表示不可以走，文件读入这 n * m个数据和起始点、结束点(起始点和结束点都是用两个数据来描述的，分别表示这个点的行号和列号)。现在要你编程找出所有可行的道路，要求所走的路中没有重复的点，走时只能是上下左右四个方向。如果一条路都不可行，则输出相应信息(用-l表示无路)。 请统一用 左上右下的顺序拓展，也就是 (0,-1),(-1,0),(0,1),(1,0)

输入描述：

​ 第一行是两个数 n，m ( 1 < n ， m < 15 )，接下来是m行n列由1和0组成的数据，最后两行是起始点和结束点。

输出描述：

​ 所有可行的路径，描述一个点时用(x，y)的形式，除开始点外，其他的都要用->表示方向。 如果没有一条可行的路则输出 -1。

样例输入：

5 6
1 0 0 1 0 1
1 1 1 1 1 1
0 0 1 1 1 0
1 1 1 1 1 0
1 1 1 0 1 1
1 1
5 6

样例输出：

(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)

提示信息：

用一个a数组来存放迷宫可走的情况，另外用一个数组b来存放哪些点走过了。每个点用两个数字来描述，一个表示行号，另一个表示列号。对于某一个点(x，y)，四个可能走的方向的点描述如下表：
　　2
1　x,y　　3
　　4
　对应的位置为：(x, y-1)，(x-1, y)，(x, y+1)，(x+1, y)。所以每个点都要试探四个方向，如果没有走过(数组b相应的点的值为0)且可以走(数组a相应点的值为1)同时不越界，就走过去，再看有没有到达终点，到了终点则输出所走的路，否则继续走下去。
　这个查找过程用search来描述如下：
procedure search(x, y, b, p)；{x，y表示某一个点，b是已经过的点的情况，p是已走过的路}
begin
　　for i:＝1 to 4 do{分别对4个点进行试探}
　　begin
　　　　先记住当前点的位置，已走过的情况和走过的路；
　　　　如果第i个点(xi，yi)可以走，则走过去；
　　　　如果已达终点，则输出所走的路径并置有路可走的信息，
　　　　否则继续从新的点往下查找search(xi，yi，b1，p1)；
　　end；
end；
　有些情况很明显是无解的，如从起点到终点的矩形中有一行或一列都是为0的，明显道路不通，对于这种情况要很快地“剪掉”多余分枝得出结论，这就是搜索里所说的“剪枝”。从起点开始往下的一层层的结点，看起来如同树枝一样，对于其中的“枯枝”——明显无用的节点可以先行“剪掉”，从而提高搜索速度。

#include<bits/stdc++.h>
using namespace std ;
#define MAX 20
// 下列变量代表迷宫的维数， 解的数量，起始坐标和出口坐标  
int n , m , num = 0 , startX , startY , endX , endY ;
int labyrinth[MAX][MAX] = { 0 } ; // 存储迷宫的二维数组 
int dx[4] = {0 , -1 , 0 , 1 } ; 
int dy[4] = {-1 , 0 , 1 , 0 } ; // 表示上下左右的扩展
// 代表所有是解的路径上的点的数量(除终点) 
vector<pair<int , int > > road ; //保存路线的向量，每个元素的有x、y坐标 
// x ,y 代表当前处理的坐标点，
void dfs(int x , int y ){
	road.push_back(make_pair(x , y )) ; // 当前坐标的赋值	
	if(x == endX && y == endY){ // 如果已经走到出口位置，输出这条路径
		for(int i = 0 ; i < road.size() ; i ++){ 
			printf("(%d,%d)" , road[i].first , road[i].second) ; 
			if(i != road.size() - 1) printf("->") ;
		}
		printf("\n") ; 
		num ++ ;// 解的数量加 1 
		return ;
	}
	// 遍历当前坐标的左，上，右，下位置的点
	for(int j = 0 ; j < 4 ; j ++){
        // 如果进行 左，上，右，下 扩展后，得到的点依旧未被访问且 在迷宫的范围内
		if(labyrinth[x + dx[j]][y + dy[j]] == 1 && 1 <= x + dx[j] <= m && 1 <= y + dy[j] <= n){
			labyrinth[x][y] = 0 ; //当前点以遍历，不可访问
			dfs(x + dx[j] , y + dy[j]) ; // 选择某个位置(左，上，右，下)，继续遍历搜索
			road.pop_back() ; // 当前元素出栈
			labyrinth[x][y] = 1 ; // 还原现场 
		}
	} 
}
int main(){
	scanf("%d%d" , &m , &n) ;// 输入迷宫的行与列的值 
	for(int i = 1 ; i <= m ; i ++){
		for(int j = 1 ; j <= n ; j ++){
			scanf("%d" , &labyrinth[i][j]) ; // 输入迷宫
		}
	}
	scanf("%d%d" , &startX , &startY) ; // 输入起始点坐标
	scanf("%d%d" , &endX , &endY) ;// 输入终点坐标
	dfs(startX , startY) ; // 从输入的起点开始 dfs
	if(num == 0) printf("-1\n") ; // 如果找不到路径，则输出 -1 
	return 0 ;
}