经过思考蒜头君终于解决了怎么计算一个迷宫的最短路问题，于是蒜头君找到一个新的迷宫图，来验证自己是否真的会计算一个迷宫的最短路。

为了检验自己计算的是否正确，蒜头君特邀你一起来计算。

输入格式

第一行输入两个整数 n 和 m，表示这是一个 n×m 的迷宫。

接下来的输入一个 n 行 m 列的迷宫。其中'@'表示蒜头君的位置，'#'表示墙，蒜头君无法通过，'.'表示路，蒜头君可以通过'.'移动，所有在迷宫最外围的'.'都表示迷宫的出口（蒜头君每次只能移动到四个与他相邻的位置——上，下，左，右）。

输出格式

输出整数，表示蒜头君逃出迷宫的最少步数，如果蒜头君无法逃出迷宫输出 -1。

数据范围

1≤n,m≤15。

输出时每行末尾的多余空格，不影响答案正确性

样例输入

9 13
#############
#@……….#
#####.#.#.#.#
#………..#
#.#.#.#.#.#.#
#.#…….#.#
#.#.#.#.#.#.#
#………..#
#####.#######

样例输出

11

样例输入

4 6
#.####
#.#.##
#…@#
######

样例输出

5

解法1：

#include
#include
using namespace std;

struct Node
{
int x,y,step;
Node(int xx,int yy,int ss):x(xx),y(yy),step(ss){ }
};

queueq;
bool mark[20][20];
int n,m,beginx,beginy,endx,endy,step=0;
int min=99999;
char map[20][20];
int dx[5]={0,0,-1,1};
int dy[5]={-1,1,0,0};
//限界函数
bool check(int r,int c){
if (r>=0&&r=0&&c<m)
return true;

return false;  复制

}

void BFS(int r,int c){
//第一步，先把起始点放入queue，设置层数step=0
q.push(Node(r,c,0));
//第二步，查找，队列非空就有机会找到
while (!q.empty())
{
//第三步，取对头
Node s = q.front();
//找到即可退出
if (map[s.x][s.y]=='.'&&(s.x==0||s.x==n-1||s.y==0||s.y==m-1))
{
cout<<s.step<<endl;
return ;
}else
{
//遍历子节点
for (int i = 0; i < 4; i++)
{
int newx=s.x+dx[i];
int newy = s.y+dy[i];

            //判断子节点是否可以通过，可通过则压栈，设置已访问  
            if (check(newx,newy)&&!mark\[newx\]\[newy\]&&map\[newx\]\[newy\]!='#')  
            {  
                mark\[newx\]\[newy\]=true;  
                q.push(Node(newx,newy,s.step+1));  
            }  
        }  
    }  
    q.pop();  
}  
cout<<"-1"<<endl;  
return;复制

}
int main(){
cin>>n>>m;
for (int i = 0; i < n; i++) { cin>>map[i];
for (int j=0; j < m; j++)
{
if (map[i][j]=='@')
{
beginx= i;
beginy=j;
}
}
}
BFS(beginx,beginy);
}

解法2：

#include
#include
using namespace std;
#include
const int INF=1e9;
const int MAX=1000+10;
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
typedef pair P;
char maze[MAX][MAX];
int N,M;
int sx,sy;//起点
int d[MAX][MAX];//到各个位置最短距离的数组
int bfs(){
queue

que;
for(int i=0;i=0&&ny>=0&&nx=INF) printf("-1\n");
else printf("%d\n",bfs());
}
return 0;
}