给定一个迷宫,入口为左上角,出口为右下角,问是否有路径从入口到出口,若有则输出一条这样的路径。注意移动可以从上、下、左、右、上左、上右、下左、下右八个方向进行。迷宫输入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; }
微信
支付宝