深度优先搜索（C++代码实现）

深度优先搜索（C++代码实现）

举个例子，比如现在你的位置为（1,1），你需要移动到一个位置（n，m），
并且路途中有多个障碍物阻挡你的前进，求出最少需要移动的次数。

对于这个问题，我们可以使用从起点开始顺时针进行移动（即：先向右，再向下，再
向左，再向上）。并且使用二维数组模拟一下地图。当碰到障碍物的时候进行优先的
顺时针的方向（右->下->左->上）总有一条路能走通，就接着继续走，直到目的地，
这是其中的一条可行的路，然后就模拟所有的路，找到最短的那条即可。

OK，分析完毕，开始写代码：

#include<iostream>
using namespace std;

int n, m, p, q, min = 999999;
int a[51][51], book[51][51];
void dfs(int x, int y, int step) {//其中的坐标为第x行的第y列，即（x,y），左上角即为（1,1）
	int next[4][2] = {
		{0,1},//向右
		{1,0},//向下
		{0,-1},//向左
		{-1,0}//向上
	};
	int tx, ty, k;
	//判断是否到达目的地
	if (x == p && y == q) {
		if (step < min) {
			min = step;
			return;
		}
	}
	for (k = 0; k <= 3; k++) {
		tx = x + next[k][0];
		ty = y + next[k][1];
		//不能越界
		if (tx<1||ty<1||tx>n||ty>m)
		{
			continue;
		}
		if (a[tx][ty]==0&&book[tx][ty]==0)
		{
			book[tx][ty] = 1;//标记一下，走过了
			dfs(tx, ty, step + 1);
			book[tx][ty] = 0;//等到尝试完，取消标记这个点
		}
	}
	return;
}

int main() {
	int i, j, starX, starY;
	cin >> n >> m;
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= m; j++)
		{
			cin >> a[i][j];//输入地图
		}
	}
	cin >> starX >> starY >> p >> q;//输入起点和终点的行列坐标
	book[starX][starY] = 1;//标记起点已经走过
	dfs(starX, starY, 0);
	cout << min;
	return 0;
}

等会儿再更新广度优先搜索。