BFS（模板）

struct node{ int x,y,step; }Node; node S,E; int n, m; char maze[maxn][maxn]; bool flag[maxn][maxn]; int X[4] = {0,0,1,-1}; int Y[4] = {1,-1,0,0}; bool judge(int x, int y){ if(x >= n || x < 0 || y >= m || y < 0){//边界约束 return false; } if(maze[x][y] == '#' || flag[x][y] == true){//没碰壁且未被访问过 return false; } return true; } int BFS(int x, int y){//返回值是走迷宫最短路 queue<node> Q; Node.x = x, Node.y = y; Q.push(Node); flag[x][y] = true; while(!Q.empty()){ node top = Q.front(); Q.pop(); if(top.x == E.x && top.y == E.y){ return top.step; } for(int i = 0; i < 4; i++){//判断队首元素相邻元素 int tx = top.x + X[i]; int ty = top.y + Y[i]; if(judge(tx,ty)){ Node.x = tx; Node.y = ty; Node.step = top.step+1; //记录层数 Q.push(Node); flag[tx][ty] = true; } } }return -1;//无法到达终点 }