走迷宫求最小步数题解

问题描述：第一行输入两个数，分别是迷宫的行数和列数，第二行输入1和0，1表示可以走，0不能走输出一个数，表示迷宫的最少步数。

遇到的问题:向函数传到二维数组时，超过了的传到二维数组上限，1000时不行，100可以

思路：基于非递归的广度搜索，从入口处，用队列收割入口位置的下标，把一个位置的所有能走的下一步收到队列里面，下次队列出去一个元素，在出去的元素基础上再收割新的元素。首个时候要判断三个条件（这个位置是否在迷宫内部、这个位置是否走过了、这个位置是不是1，能不能走），根据这三个条件，我们要建立一个队列，一个辅助数组，一个储存0和1元素的数组。

感想：搜索一般都要建立一个二维数组或者两个一维数组来储存{1,-1,0}这三个值，为的使工作下标变化。

一般走迷宫的套路就是在一个while循环里面对每个满足三个条件的下标测试，满足就标记一下，不满足的就不管。

#include<iostream>
using namespace std;
//判断条件需要三个，一个是坐标是否在这个数组内部，一个是这个坐标是否被走过，一个是这个坐标是否能走 
//1能走；0是墙，不能走 
struct N{
	int x;
	int y;
}queue[100];
int top=0;
int base=0;
int dx[4]={-1,1,0,0};//上下左右的坐标移动 
int dy[4]={0,0,1,-1};//上下左右的坐标移动 
void Pop(int x,int y){
	queue[top].x=x;
	queue[top].y=y;
	top++;
}
int Empty(){
	if(base==top)
	return 0;//队列空
	else return 1;//队列不空 
}
void Push(int &x,int &y){//传入两个值即为队列尾部元素 
	x=queue[base].x;
	y=queue[base].y;
	base++;
}
int bfs(int nums[100][100],int d[100][100],int n,int m){
	int x=0,y=0;//队列中的x和y 
	int x1=0,y1=0;//新的x和y 
	Pop(0,0);//存入起点,不用判断nums值是否为1，肯定能走 
	while(Empty()){
		Push(x,y);//出队列，把队尾元素输出来 
		for(int i=0;i<4;i++){
			x1=x+dx[i];y1=y+dy[i];//新的坐标
		if((0<=x1<n)&&(0<=y1<m)&&(d[x1][y1]==0)&&(nums[x1][y1]==1)){//等于0操作证明，新的下标没有走过 
			d[x1][y1]=d[x][y]+1;
			Pop(x1,y1);
		}		
		} 
	}
	return d[n-1][m-1];
}
int main(){
	int nums[100][100];//储存迷宫，0和1
	int d[100][100];//用于判断走过没、储存距离
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++) 
	for(int j=0;j<m;j++){
		cin>>nums[i][j];
		d[i][j]=0;
	}
	cout<<bfs(nums,d,n,m)+1<<endl;//需要走的步数，加1是因为第一步需要加上，初始化累加的头是0 
	return 0;
}