在一个n*n的矩阵里走，从原点（0,0）开始走到终点（n-1,n-1），只能上下左右4个方向走，只能在给定的矩阵里走，求最短步数。n*n是01矩阵，0代表该格子没有障碍，为1表示有障碍物。 int mazeArr[maxn][maxn]; //表示的是01矩阵 int stepArr[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; //表示上下左右4个方向 int visit[maxn][maxn]; //表示该点是否被访问过，防止回溯，回溯很耗时。 解题思路： BFS找出来的是最短路径，如果用DFS，那么寻找出来的不是最短路径。 我们先对原点的上下左右进行访问，如果上下左右的点非障碍物，并且还没访问过，那么就将这些点入队列，并设置为已经访问，然后再依次把这些点出队列，并且重复之前的步骤对这些点的进行上下左右访问。。。。如果最后访问到终点（n-1，n-1），则结束 代码如下：
#include
using namespace std;
//定义迷宫的行列
#define ROW_COL 4
//定义一个结构体，表示经过的点路径
struct Node
{
int x;
int y;
int step;
};
//赋值
Node fuzhi(int x,int y,int step)
{
Node p;
p.x=x;
p.y=y;
p.step=step;
return p;
}
//实现一个循环队列
//=====================================
#define QueueSize 30
typedef struct
{
Node Seq[QueueSize];
int front;
int rear;
int count;
}RQueue;
RQueue Q;
void Initiate_Queue(RQueue *Q)
{
Q->front=0;
Q->rear=0;
Q->count=0;
}
void AppendQueue(RQueue *Q,Node data)
{
if(Q->count>=QueueSize)
{
cout<<"overflow"<
Seq[Q->rear]=data; Q->rear=(Q->rear+1)%QueueSize; Q->count++; } int QueueNotEmpty(RQueue *Q) { if(Q->count!=0) return 1; else return 0; } Node DeleteQueue(RQueue *Q) { if(Q->count<=0) { cout<<"empty"<
Seq[Q->front]; Q->front=(Q->front+1)%QueueSize; Q->count--; return d; } //======================= //迷宫图的矩阵 int mazeArr[4][4]= { {0,0,1,1}, {0,1,1,0}, {0,0,1,0}, {0,1,0,0} }; int visit[ROW_COL][ROW_COL]; //表示上下左右 int stepArr[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; //对其进行BFS，找出的路径为最短路径，注意二位数组的形参是int (*mazeArr)[4] int BFS(int (*mazeArr)[4],Node node,int n) { for(int i=0;i
=0 &&y>=0&&x