给定一个迷宫，入口为左上角，出口为右下角，问是否有路径从入口到出口，若有则输出一条这样的路径。注意移动可以从上、下、左、右、上左、上右、下左、下右八个方向进行。迷宫输入0表示可走，输入1表示墙。易得可以用1将迷宫围起来避免边界问题。
本题采用BFS算法给出解。注意，利用BFS算法给出的路径必然是一条最短路径。
/*
迷宫问题（八方向）
input:
1
6 8
0 1 1 1 0 1 1 1
1 0 1 0 1 0 1 0
0 1 0 0 1 1 1 1
0 1 1 1 0 0 1 1
1 0 0 1 1 0 0 0
0 1 1 0 0 1 1 0
output:
YES
(1,1) (2,2) (3,3) (3,4) (4,5) (4,6) (5,7) (6,8)
*/
#include<iostream>
#include<queue>
#include<stack>
using namespace std;
struct point{
//横坐标纵坐标
int x;
int y;
};
int **Maze; //初始化迷宫
point **Pre; //保存任意点在路径中的前一步
point move[8]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}}; //移动方向，横竖斜都可以，八个方向
void Create(int row,int column){
//创建迷宫，注意到用0表示可走，1表示墙，将整个输入的迷宫再用墙围着，处理的时候就不用特别注意边界问题
int i,j;
for(i=0; i<row+2; i++)
Maze[i][0] = Maze[i][column+1] = 1;
for(j=0; j<column+2; j++)
Maze[0][j] = Maze[row+1][j] = 1;
for(i=1; i<=row; i++){
for(j=1; j<=column; j++){
cin>>Maze[i][j];
}
}
}
bool MazePath(int row,int column,int x,int y){
//判断是否有路径从入口到出口，保存该路径（队列）
if(x == row && y == column)return true;
queue<point> q; //用于广度优先搜索
point now; //当前位置
now.x = x;
now.y = y;
q.push(now);
Maze[now.x][now.y] = -1;
while(!q.empty()){
now = q.front();
q.pop();
for(int i=0; i<8; i++){
if(now.x + move[i].x == row && now.y + move[i].y == column){
Maze[now.x + move[i].x][now.y + move[i].y] = -1;
Pre[row][column] = now;
return true;
}
if(Maze[now.x + move[i].x][now.y + move[i].y] == 0){
point temp; //下个位置
temp.x = now.x + move[i].x;
temp.y = now.y + move[i].y;
q.push(temp);
Maze[temp.x][temp.y] = -1;
Pre[temp.x][temp.y] = now;
}
}
}
return false;
}
void PrintPath(int row,int column){
//输出最短路径
point temp; //保存位置
stack<point> s; //保存路径序列
temp.x = row;
temp.y = column;
while(temp.x != 1 || temp.y != 1){
s.push(temp);
temp = Pre[temp.x][temp.y];
}
cout<<"(1,1)";
while(!s.empty()){
temp = s.top();
cout<<' '<<'('<<temp.x<<','<<temp.y<<')';
s.pop();
}
cout<<endl;
}
int main(){
int t; //用例数量
int row; //迷宫行数
int column; //迷宫列数
cin>>t;
while(t--){
cin>>row>>column;
Maze = new int*[row + 2];
Pre = new point*[row + 2];
for(int i=0; i<row+2; i++){
Maze[i] = new int[column + 2];
Pre[i] = new point[column + 2];
}
Create(row,column);
if(MazePath(row,column,1,1)){
cout<<"YES"<<endl;
PrintPath(row,column);
}
else cout<<"NO"<<endl;
}
return 0;
}
#include "Define.h"
using namespace DUI_API;
typedef struct __Pos {
int x, y;
bool operator ==(const struct __Pos &p) {
if (x == p.x && y == p.y) return true;
return false;
}
void operator =(const struct __Pos &p) {
x = p.x;
y = p.y;
}
}_Pos;
_Pos nextPos(_Pos pos,int direct) {
switch (direct)
{
case 0: {
pos.y++;
break;
}
case 1: {
pos.x--;
break;
}
case 2: {
pos.y--;
break;
}
case 3: {
pos.x++;
break;
}
}
return pos;
}
int MiGong(int ME[][6],Vector<_Pos>&vec, _Pos &startPos, _Pos &endPos,const int M = 6, const int N=6) {
_Pos _stack,_next;
ME[startPos.x][startPos.y] = -1;
_stack = startPos;
vec.push_back(_stack);
int j = 0;
bool find = false;
while (vec.size()){
_stack = vec.Last();
if (_stack == endPos) {
vec.push_back(_stack);
return 1;
}
find = false;
for (int i = 0; i < 4; i++) {
_next = nextPos(_stack,i);
if (ME[_next.x][_next.y] == 0) {
vec.push_back(_next);
ME[_next.x][_next.y] = -1;
find = true;
}
}
if (!find) vec.pop_back();
if (++j == 40) break;
}
return 0;
}
int main()
{
int times1 = time(NULL);
typedef _Pos TT;
Vector<TT>vec;
Vector<TT>::iterator it;
const int M = 6, N = 6;
int i, j;
int ME[M][N] = {
1,1,1,1,1,1,
1,0,1,0,0,1,
1,0,0,0,0,1,
1,0,1,1,0,1,
1,0,0,1,0,1,
1,1,1,1,1,1};
for (i = 0; i < M; i++) {
for (j = 0; j < N; j++) {
printf("%d ", ME[i][j]);
}
printf("\n");
}
_Pos s = { 1, 1 }, e = { 4, 4 };
MiGong(ME,vec,s,e);
i = 0;
for (it = vec.begin(); it != vec.end(); it++) {
printf("(%d,%d) ,", it->x,it->y);
if (i++ == 4) {
printf("\n");
}
}
int times2 = time(NULL);
printf("耗费时间：%d\n",times2 -times1);
system("pause");
return 0;
}
微信
支付宝
