#include<iostream>
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"<<endl;
		return ;
	}
	Q->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"<<endl;
		exit(0);
	}
	Node d;
	d=Q->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<ROW_COL;i++)
		for(int j=0;j<ROW_COL;j++)
			visit[i][j]=0;
	Node N;
	Initiate_Queue(&Q);
	AppendQueue(&Q,node);
	while(QueueNotEmpty(&Q))
	{
		N=DeleteQueue(&Q);
		if(N.x==n-1 &&N.y==n-1)
		{
			return N.step;
		}
		visit[N.x][N.y]=1;
		//对该点的上下左右进行遍历，如果符合条件，就入队列
		for(int i=0;i<4;i++)
		{
			int x=N.x+stepArr[i][0];
			int y=N.y+stepArr[i][1];
			if(x>=0 &&y>=0&&x<n&&y<n&&!visit[x][y]&& mazeArr[x][y]==0)
			{
				visit[x][y]=1;
				N=fuzhi(x,y,N.step+1);
				AppendQueue(&Q,N);
			}
		}
	}
	return -1;
}


void main()
{
	Node node;
	node=fuzhi(0,0,0);
	cout<<BFS(mazeArr,node,ROW_COL);
	getchar();
}