dfs之解救小哈

问题

分析

先让小哼往右边走，然后一直尝试下去，直到走不通的时候再回到这里。

代码实现

#include <stdio.h>
int book[51][51],n, m,a[51][51],p,q,min=999999;

void dfs(int x, int y, int step) {
	int next[4][2] = { {0,1} ,//向右走
						{1,0},//向下走
						{-1,0},//向左走
						{0,-1} };//向上走
	int tx, ty, k;
	//判断是否到达小哈的位置
	if (x == p && y == q) {
		//更新最小值
		if (step < min) {
			min = step;
		}
		//printf("%d", step);
		return;//返回上一步，很重要
	}
	for (k = 0; k <= 3; k++) {
		//计算下一个点的坐标
		tx = x + next[k][0];
		ty = y + next[k][1];
		//判断是否越界
		if (tx<1 || tx>n || ty<1 || 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, startx, starty;
	printf("你要输入几行几列的迷宫：");
	scanf_s("%d %d", &n, &m);
	printf("请输入迷宫（0表示空地，1表示障碍物）：\n");
	//读入迷宫
	for(i=1;i<=n;i++)
		for (j = 1; j <= m; j++) {
			scanf_s("%d", &a[i][j]);
		}
	
	printf("请输入初始位置：");
	scanf_s("%d %d", &startx,&starty);
	book[startx][starty] = 1;//初始位置做标记
	printf("请输入小哈的位置：");
	scanf_s("%d %d", &p, &q);
	dfs(startx,starty,0);//从初始步数为0
	printf("%d", min);
	getchar(); getchar();
	return 0;

}

输入

5 4
0 0 1 0
0 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1
1 1 4 3

输出

7