文档章节

模拟求解迷宫问题(DFS+BFS)

N3verL4nd
 N3verL4nd
发布于 2017/03/25 10:45
字数 1176
阅读 51
收藏 0

代码下载:http://download.csdn.net/detail/lgh1992314/5326941

迷宫是实验心理学中一个古典问题。以一个n*m的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。入口在左上方(1,1)处,出口在右下方(n,m)处。

要求求出从迷宫入口到出口有无通路的最短路径。

生成迷宫(调用的c语言中的srand和rand函数):

#include <iostream>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <windows.h>
using namespace std;
#define MAX 1000
int map[MAX][MAX];

void CreateMap(int n, int m)              //1代表墙壁 0代表通路
{
      for(int i = 1; i <= n; i++)
      {
          for(int j = 1; j <= m; j++)
          {
              map[i][j] = rand() % 2;
              Sleep(5);
          }
      }
}

int main()
{
    freopen("map.txt", "w", stdout);
    int n, m;
    srand((unsigned)time(NULL));
    memset(map, -1, sizeof(map));
    cin >> n >> m;
    CreateMap(n, m);
    map[1][1] = 0;
    map[n][m] = 0;
    for(int i = 1; i <= n; i++)
      {
          for(int j = 1; j <= m; j++)
          {
              if(j != m)
              {
                   cout << map[i][j] << " ";
              }
              else
              {
                  cout << map[i][j] << endl;
              }
              
          }
      }
    return 0;
}
迷宫搜索:(BFS)

路径标记使用了API:SetConsoleTextAttribute

#include <iostream>
#include <queue>
#include <cstring>
#include <fstream>
#include <cstdio>
#include <Windows.h>
using namespace std;
#define MAX 1000
#define turn 8
typedef struct Point
{
	int x;
	int y;
	int cnt;
}Point;
const int moves[turn][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
int map[MAX][MAX];
bool visited[MAX][MAX];
int color[MAX][MAX];
int n, m, ans;
queue<Point>Q;
Point back[MAX][MAX], path[MAX];

void LoadMap()
{
	cin >> n >> m;
	fstream cin("map.txt");
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			cin >> map[i][j];
		}
	}
	cin.close();
}

void ShowMap()
{
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			if(j != m)
			{
				cout << map[i][j] << " ";
			}
			else
			{
				cout << map[i][j] << endl;
			}

		}
	}
}

void bfs(int x, int y)
{
	while(!Q.empty())
	{
		Q.pop();
	}
	Point pre, next;
	pre.x = x;
	pre.y = y;
	pre.cnt = 0;
	visited[pre.x][pre.y] = true;
	Q.push(pre);
	while(!Q.empty())
	{
		pre = Q.front();
		Q.pop();
		if(pre.x == n && pre.y == m)
		{
			ans = pre.cnt;
			break;
		}
		for(int i = 0; i < turn; i++)
		{
			next.x = pre.x + moves[i][0];
			next.y = pre.y + moves[i][1];
			if(next.x >= 1 && next.x <= n && next.y >= 1 && next.y <= m && !visited[next.x][next.y] && map[next.x][next.y] == 0)
			{
				back[next.x][next.y] = pre;
				next.cnt = pre.cnt + 1;
				visited[next.x][next.y] = true;
				Q.push(next);
			}
		}
	}
	for(int i = ans; i >= 0; i--)
	{
		path[i] = pre;
		pre = back[pre.x][pre.y];
	}
}

void ShowSetp()
{
	HANDLE handle;
	handle = GetStdHandle(STD_OUTPUT_HANDLE);
	memset(color, 0, sizeof(color));
	for(int i = 0; i <= ans; i++)
	{
		printf("(%d, %d)\n",path[i].x,path[i].y);
		color[path[i].x][path[i].y] = 1;
	}
	int count = 0;
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			if(color[i][j] == 1)
			{
				SetConsoleTextAttribute(handle,  
										FOREGROUND_GREEN |  
										FOREGROUND_INTENSITY);  
				cout << map[i][j] << " ";
			}
			else
			{
				SetConsoleTextAttribute(handle,  
					FOREGROUND_RED |  
					FOREGROUND_INTENSITY);  
				cout << map[i][j] << " ";
			}
		}
		cout << endl;
		count++;
	}
}

/*
void BcakTrack(int x, int y)
{
	if(back[x][y].x == 1 && back[x][y].y == 1)
	{
		printf("(1, 1)\n");
		return;
	}
	else
	{
		BcakTrack(back[x][y].x, back[x][y].y);
		printf("(%d, %d)\n", back[x][y].x, back[x][y].y);
	}
}*/																		

int main()
{
	LoadMap();
	ShowMap();
	memset(visited, false, sizeof(visited));
	ans = 0;
	bfs(1, 1);
	if(ans != 0)
	{
		cout << "It will take " << ans << " setps to the destination" << endl;
		ShowSetp();
		//BcakTrack(n, m);
	}
	else
	{
		cout << "Can't Find a way to the destination" << endl;
	}
	return 0;
}

测试程序(调用了bat,拒绝手动,主要还是懒=。=)

Monitoring.bat

@shift
@echo off
setlocal
MODE con: COLS=40 lines=15
color 0a
title  迷宫    by_N3verL4nd
:Start
for /L %%a in (
15,-1,0
) do (
echo.
echo.
echo.
echo.
echo    ☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆
echo    ☆  每隔15秒自动启动迷宫程序    ☆
echo    ☆        还剩余 %%a 秒           ☆
echo    ☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆
ping 127.0.0.1 -n 2 >nul 
cls
)
echo 23 39 | CreateMap.exe
ping 127.0.0.1 -n 2 >nul
start maze_bfs.bat
start maze_dfs.bat
goto Start
maze_bfs.bat

@echo off
title Maze_bfs...
echo 23 39 | maze_bfs.exe
ping 127.0.0.1 -n 10 > nul
exit
maze_dfs.bat
@echo off
title Maze_dfs...
echo 23 39 | maze_dfs.exe
ping 127.0.0.1 -n 10 > nul
exit



DFS:

#include <iostream>
#include <queue>
#include <cstring>
#include <fstream>
#include <cstdio>
#include <Windows.h>
using namespace std;
#define MAX 1000
#define turn 8
typedef struct Point
{
	int x;
	int y;
}Point;
const int moves[turn][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
int map[MAX][MAX];
bool visited[MAX][MAX];
int color[MAX][MAX];
int n, m, ans;
bool flag;
Point back[MAX][MAX], path[MAX];

void LoadMap()
{
	cin >> n >> m;
	fstream cin("map.txt");
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			cin >> map[i][j];
		}
	}
	cin.close();
}

void ShowMap()
{
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			if(j != m)
			{
				cout << map[i][j] << " ";
			}
			else
			{
				cout << map[i][j] << endl;
			}

		}
	}
}

void dfs(int x, int y)
{
	if(x == n && y == m)
	{
		flag = true;
		Point pre;
		pre.x = n;
		pre.y = m;
		while (back[pre.x][pre.y].x != 0 && back[pre.x][pre.y].y != 0)
		{
			pre = back[pre.x][pre.y];
			ans++;
		}
		//cout << "ans = " << ans <<  endl;
		pre.x = n;
		pre.y = m;
		for(int i = ans; i >= 0; i--)
		{
			path[i] = pre;
			pre = back[pre.x][pre.y];
		}
		for(int i = 0; i <= ans; i++)
		{
			printf("(%d, %d)\n",path[i].x,path[i].y);
		}
		return;
	}

	for(int i = 0; i < turn; i++)
	{
		int p = x + moves[i][0];
		int q = y + moves[i][1];
		if(p >= 1 && p <= n && q >= 1 && q <= m && !visited[p][q] && map[p][q] == 0)
		{
			visited[p][q] = true;
			back[p][q].x = x;
			back[p][q].y = y;
			dfs(p, q);
			if(flag) return;
			visited[p][q] = false;
		}
	}
}

void ShowSetp()
{
	HANDLE handle;
	handle = GetStdHandle(STD_OUTPUT_HANDLE);
	memset(color, 0, sizeof(color));
	for(int i = 0; i <= ans; i++)
	{
		printf("(%d, %d)\n",path[i].x,path[i].y);
		color[path[i].x][path[i].y] = 1;
	}
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			if(color[i][j] == 1)
			{
				SetConsoleTextAttribute(handle,  
										FOREGROUND_GREEN |  
										FOREGROUND_INTENSITY);  
				cout << map[i][j] << " ";
			}
			else
			{
				SetConsoleTextAttribute(handle,  
					FOREGROUND_RED |  
					FOREGROUND_INTENSITY);  
				cout << map[i][j] << " ";
			}
		}
		cout << endl;
	}
}
																	
int main()
{
	LoadMap();
	ShowMap();
	memset(visited, false, sizeof(visited));
	ans = 0;
	visited[1][1] = true;
	flag = false;
	dfs(1, 1);
	if(flag)
	{
		cout << "It will take " << ans << " setps to the destination" << endl;
		ShowSetp();
	}
	else
	{
		cout << "Can't Find a way to the destination" << endl;
	}
	return 0;
}

话说,记录这张图片等了好久的说。结点一多,DFS的效率就降低了。


© 著作权归作者所有

N3verL4nd
粉丝 1
博文 379
码字总数 481243
作品 0
朝阳
私信 提问
数据结构java迷宫的路径搜索方式与迷宫数据存储模式

@小代 你好,想跟你请教个问题: 实现一个以链表作存储结构的栈类型,然后编写一个求解迷宫的非递归程序 跟 在迷宫中进行路径搜索时,可采用深度优先搜索或广度优先搜索的策略 并且用二维数组...

问题
2014/12/28
197
0
游戏与常用的五大算法---下篇

前言: 心是一个人的翅膀,心有多大,世界就有多大。很多时候限制我们的,不是周遭的环境,也不是他人的言行,而是我们自己!看不开,放不下,忘不了,把自己囚禁在灰暗的记忆里;不敢想,不...

loving_forever_
2017/01/08
0
0
菜鸟的进击——C语言实现老鼠走迷宫

老鼠走迷宫,一只实验室的小老鼠被用来做迷宫智力实验。科学家在迷宫的一角放上一块奶酪,小老鼠要在最快时间内找到奶酪。 老鼠走迷宫是递回求解的基本题型,我们在二维阵列中使用2表示迷宫墙...

柳猫
2018/06/01
0
0
UVA ~ 816 ~ Abbott's Revenge (BFS + 打印路径)

题意:有一个最多包含9*9个交叉点的迷宫。输入起点,离开起点时的朝向和终点,求一条最短路(多解时任意输出一个即可)。 这个迷宫的特殊之处在于:进入一个交叉点的方向(用NEWS这四个字母分...

zscdst
2018/05/13
0
0
龙生龙,凤生凤,老鼠儿子,会打洞,C语言经典算法之老鼠走迷宫

老鼠走迷官 老鼠走迷宫是递回求解的基本题型,我们在二维阵列中使用2表示迷宫墙壁,使用1来表示老鼠的行走路径,试以程式求出由入口至出口的路径。 解析 老鼠的走法有上、左、下、右四个方向...

这个人很懒什么都没留下
03/29
0
0

没有更多内容

加载失败,请刷新页面

加载更多

只需一步,在Spring Boot中统一Restful API返回值格式与统一处理异常

统一返回值 在前后端分离大行其道的今天,有一个统一的返回值格式不仅能使我们的接口看起来更漂亮,而且还可以使前端可以统一处理很多东西,避免很多问题的产生。 比较通用的返回值格式如下:...

晓月寒丶
昨天
59
0
区块链应用到供应链上的好处和实际案例

区块链可以解决供应链中的很多问题,例如记录以及追踪产品。那么使用区块链应用到各产品供应链上到底有什么好处?猎头悬赏平台解优人才网小编给大家做个简单的分享: 使用区块链的最突出的优...

猎头悬赏平台
昨天
28
0
全世界到底有多少软件开发人员?

埃文斯数据公司(Evans Data Corporation) 2019 最新的统计数据(原文)显示,2018 年全球共有 2300 万软件开发人员,预计到 2019 年底这个数字将达到 2640万,到 2023 年达到 2770万。 而来自...

红薯
昨天
65
0
Go 语言基础—— 通道(channel)

通过通信来共享内存(Java是通过共享内存来通信的) 定义 func service() string {time.Sleep(time.Millisecond * 50)return "Done"}func AsyncService() chan string {retCh := mak......

刘一草
昨天
58
0
Apache Flink 零基础入门(一):基础概念解析

Apache Flink 的定义、架构及原理 Apache Flink 是一个分布式大数据处理引擎,可对有限数据流和无限数据流进行有状态或无状态的计算,能够部署在各种集群环境,对各种规模大小的数据进行快速...

Vincent-Duan
昨天
60
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部