欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

DFS走迷宫

程序员文章站 2022-05-20 21:35:46
...

下面给出DFS算法走迷宫的代码:

#include <stdio.h>

char map[50][51];    //地图上限50*50 
int sign[50][50];     //标记 
int next[4][2] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
int n, m;    //实际地图行数、列数 
int endy, endx;     //终点位置 
int min = 99999999;

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

//构造一个盏来记录走迷宫的路径
struct Node
{
	int y;
	int x;
};

struct Stack
{
	Node * pbase;
	int top;
};

void StackInit(Stack * pstack){
	pstack->pbase = new Node[100];
	pstack->top = 0;
}

void StackPush(Stack * pstack, int y, int x){
	Node node;
	node.y = y;
	node.x = x;
	pstack->pbase[pstack->top] = node;
	++pstack->top;
}

void StackCopy(Stack * pstack1, Stack * pstack2){
	pstack2->top = pstack1->top;
	for (int i = 0; i<pstack2->top; i++)
	{
		pstack2->pbase[i] = pstack1->pbase[i];
	}
}

void StackPop(Stack * pstack){
	--pstack->top;
}

Stack stack;
Stack minstack;

//深度优先搜索 
//最好对已有的步数与min相比,如果说比已有的成功下的话,应该暂停!!!!
void dfs(int y, int x, int step){
	int ty, tx;
	if (y == endy&&x == endx)
	{
		if (step<min)
		{
			StackCopy(&stack, &minstack);
			min = step;
		}
		return;
	}

	for (int i = 0; i<4; i++)
	{
		ty = y + next[i][0];
		tx = x + next[i][1];
		if (ty >= 0 && ty<n&&tx >= 0 && tx<m&&map[ty][tx] != '#'&&sign[ty][tx] == 0)
		{
			StackPush(&stack, ty, tx);
			sign[ty][tx] = 1;
			dfs(ty, tx, step + 1);
			StackPop(&stack);
			sign[ty][tx] = 0;
		}
	}
	return;
}

int main(int argc, char** argv) {
	freopen("input.txt", "r", stdin);

	printf("请输入行数和列数:");
	scanf("%d%d", &n, &m);
	printf("请创建地图:\n");
	for (int i = 0; i<n; i++)
	{
		scanf("%s", &map[i]);
	}
	printf("创建的地图如下:\n");
	for (int i = 0; i<n; i++)
	{
		printf("%s\n", map[i]);
	}
	printf("请输入起点(y,x):");
	int starty, startx;
	scanf("%d%d", &starty, &startx);
	printf("请输入终点(y,x):");
	scanf("%d%d", &endy, &endx);
	sign[starty][startx] = 1;

	StackInit(&stack);
	StackInit(&minstack);

	dfs(starty, startx, 0);
	printf("最短路程为%d\n", min);

	printf("最短路径为:\n");
	map[starty][startx] = 's';    //用字符's'表示起点 
	for (int i = 0; i<minstack.top; i++)
	{
		map[minstack.pbase[i].y][minstack.pbase[i].x] = '>';
	}
	for (int i = 0; i<n; i++)
	{
		printf("%s\n", map[i]);
	}
	return 0;       
}

其中输入input.txt如下:

5 5 
.#.#.
.#...
.#.#.
.#.#.
...#.
0 0

4 4

运行的结果截图:

DFS走迷宫

相关标签: 迷宫问题