C++终于解决dfs回溯法过程中的环形循环问题了，就是用visit数组记录所有走过的结点啊

C++终于解决dfs回溯法过程中的环形循环问题了，就是用visit数组记录所有走过的结点啊，一定要记得每一步回溯完了要撤销影响，包括对visit数组，以及对于步数s进行撤销影响

贴一下九坤笔试

题目：青蛙走亲戚

一共有m座岛，小青蛙在1号岛，亲戚在m号岛，有的岛屿之间存在相连的水路，只不过需要花费一定的天数才能通过水路到达另一座岛，小青蛙有一个指标叫做：体力值n，代表小青蛙能够不吃不喝走n天。程序的输入为：n（初始体力值），m（岛屿总数），接下来是m行m列的矩阵A，A[i][j]代表从第i座岛屿到第j座岛屿的水路需要A[i][j]天才能通过，如果A[i][j]等于-1，代表这两座岛之间不通，只有青蛙的体力值大于两座岛屿之间水路的花费才能通过，否则就会饿死在路上，但是青蛙可以选择在原岛屿花费一天的时间寻找食物，把体力值恢复到初始的水平n， 要求：输出青蛙从第一座岛屿到达第m座岛屿花费的最少天数。

示例

输入：
5 5
0 1 1 2 -1
1 0 2 4 -1
1 2 0 2 5
2 4 2 0 2
-1 -1 5 2 0

输出：
4

代码如下：注意C++如何定义二维数组，如何把二维数组作为参数，如果涉及到动态二维数组，请参考下面这个博客园链接：添加链接描述

#include
#include 
#include 
using namespace std;
int step = 99999;

//      当前体力值n， 当前所在岛屿i， 存放已走过的结点的Set：visit， 岛屿总数m， 矩阵b[100][100], 初始体力值p
void dfs(int n, int s, int i, set visit, int m, int b[][100], int p) {
	if (i == m - 1) {
		if (s < step) {
			step = s;
		}
		return;
	}

	for (int j = 0; j < m; j++) {
		if ( visit.find(j) != visit.end()) {
			continue;
		}
		if (b[i][j] != -1) {
			if (n >= b[i][j]) {
				visit.insert(j);
				dfs(n - b[i][j], s + b[i][j], j, visit, m, b, p);
				visit.erase(j);
			}
			else {
				s++;
				n = p;
				visit.insert(j);
				dfs(n - b[i][j], s + b[i][j], j, visit, m, b, p);
				s--;
				visit.erase(j);
			}
		}
	}



}

int main() {

	int n = -1;
	int m = -1;
	cin >> n;
	cin >> m;

	int a[100][100];
	set visit;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < m; j++) {
			cin >> a[i][j];
		}
	}
	int flag = 0;
	for (int i = 0; i < m - 1; i++) {
		if (a[i][m - 1] != -1) {
			flag = 1;
			break;
		}
	}
	if (flag == 0) {
		cout << "-1";
		return 0;
	}


	visit.insert(0);
	dfs(n, 0, 0, visit, m, a, n);
	cout << step;
	return 0;


}