#include <iostream> #include <queue> using namespace std; struct node { int x,y; int step; }st,ed; const int maxn=100; int n,m;//图的边界 int gx,gy;//终点位置 int book[maxn][maxn];//记录位置是否走过 int a[maxn][maxn];//存放图的内容 //以四个方向为例,上下左右 int dx[4] = {0,0,-1,1}; int dy[4] = {1,-1,0,0}; int bfs(int x,int y) { queue <node> q;//开一个队列 // 对起点初始化 st.x = x; st.y = y; st.step = 0; // 初始层次为 0 //memset(vis, false, sizeof(vis)); vis[x][y] = 1; // 标记初始位置已被走过 q.push(st); while(!q.empty()) // 直到队列为空 或 找到终点后,终止循环 { st = q.front(); // 将起点更新为队列中的第一个结构 q.pop(); // 然后将队列中第一个结构删除 // 找到终点,就结束函数,并返回此时层数 if(st.x==gx && st.y==gy) return st.step; for(int i=0; i<4; i++) { ed.x = st.x + dx[i]; ed.y = st.y + dy[i]; ed.step = st.step + 1; //层数加一 // 若该位置已走过,则进入下一循环,避免重复 // 若超出边界,则进入下一循环 // 其中 n、m 为边界 if(vis[ed.x][ed.y] || map[ed.x][ed.y]=='题目条件' || ed.x<0 || ed.x>=n || ed.y<0 || ed.y>=m) continue; — if(vis[ed.x][ed.y] || map[ed.x][ed.y]=='题目条件' || ed.x<0 || ed.x>=n || ed.y<0 || ed.y>=m) continue; vis[ed.x][ed.y] = 1; //标记该位置已走过 // 若还未到终点,则将其放入队列,变成下次调用的起点 q.push(ed); } } return -1; // 若找不到终点,则按题目要求返回特定值 } int main() { int sx, sy; //起点 scanf("%d %d", &n, &m); //读入边界 scanf("%d %d", &sx, &sy); //读入起点 scanf("%d %d", &gx, &gy); //读入终点 for(int i=0; i<n; i++) for(int j=0; j<m; j++) scanf("%c", &a[i][j]); if(sx==gx && sy==gy) printf("0\n"); else printf("%d\n", bfs(sx, sy)); return 0; }