## 模拟求解迷宫问题（DFS+BFS） 原

N3verL4nd

``````#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;
}``````

``````#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];

{
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()
{
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;
}``````

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];

{
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()
{
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;
}``````

### N3verL4nd

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

2014/12/28
197
0

loving_forever_
2017/01/08
0
0

2018/06/01
0
0
UVA ~ 816 ~ Abbott's Revenge （BFS + 打印路径）

zscdst
2018/05/13
0
0

03/29
0
0

59
0

28
0

65
0
Go 语言基础—— 通道(channel)

58
0