典型的BFS，找到起点直接进行搜搜即可。要注意的就是层数的处理。坐标到id的转换。还有就是要尽早判断是否达到终点。
代码注释很详细，最后面两个函数是一开始写的 用抽取邻接矩阵+Dijkstra 来算的，很麻烦 头脑一热的结果。。
#include <vector> #include <queue> #include <iostream> using namespace std; int map[31][31]={0}; int M,N,M1,M2; struct Point { int x; int y; int lay;//层数 用来计算结果 }; Point s;//起点 Point e;//终点 int Graph[31*31][31*31]={0}; inline int getID(int x,int y){ if(x<=M and x>=1 and y>=1 and y<=N){ if(map[x][y]!=0 and map[x][y]!=2)//不是水和沼泽才返回 return (x-1) * N + y; } return -1; } inline void getPoint(int id, int& x,int& y){ y = id % N; if(y==0) y = N; x = id / N ; } void init(){ cin>>M>>N>>M1>>M2; for (int i = 1; i <= M; ++i) { for (int j = 1; j <= N; ++j) { cin>>map[i][j]; if(map[i][j]==3){ s.x = i; s.y = j; }else if(map[i][j]==4){ e.x = i; e.y = j; } } } } int bfs(){ //八个方向 int dx[8] = {M1,M1,-M1,-M1,M2,M2,-M2,-M2}; int dy[8] = {M2,-M2,M2,-M2,M1,-M1,M1,-M1}; queue<Point> q;//BFS的队列 s.lay = 0;//表示层数 q.push(s); bool vis[31*31] = {0}; int res=0; while(!q.empty()){ Point cur = q.front(); if(cur.x == e.x and cur.y == e.y)//其实这步没必要..早期代码遗留 break; q.pop(); res = cur.lay; vis[getID(cur.x,cur.y)] = true; //访问状态更改 for (int i = 0; i < 8; ++i) { int x = cur.x + dx[i]; int y = cur.y + dy[i]; int newid = getID(x,y); if(newid!=-1 and !vis[newid]){ Point p; p.x = x ; p.y = y; p.lay = cur.lay + 1; if(x==e.x and y==e.y)//找到终点了 return p.lay; q.push(p); vis[newid] = true;//访问状态更改 } } } return res; } int main(int argc, char const *argv[]) { //最短路径问题 init(); //另外一种方法就是抽取邻接矩阵 然后运用最短路径d算法 //buildAdjMap(); //cout<<dijkstra()<<endl; cout<<bfs()<<endl; return 0; } void buildAdjMap(){//构造邻接矩阵 int dx[8] = {M1,M1,-M1,-M1,M2,M2,-M2,-M2}; int dy[8] = {M2,-M2,M2,-M2,M1,-M1,M1,-M1}; for (int i = 1; i <= M; ++i){ for (int j=1; j <= N; ++j){ int x,y; int fromID = getID(i,j); for(int k = 0; k < 8 ; ++k){//遍历8个方向 x = i + dx[k]; y = j + dy[k]; int endID = getID(x,y); if(endID != -1){ Graph[fromID][endID]=1; Graph[endID][fromID]=1;//无向图 } } } } } int dijkstra(){//最短路径算法 写的太麻烦了 主要是想试试好不好使 int res = 0; int cnt = M*N;//总点数目 int begin = getID(s.x, s.y);//起点 int end = getID(e.x, e.y);//终点 const int INF = 9999999; int D[31*31];//存储临时距离 for (int i = 1; i <= cnt; ++i) D[i] = Graph[begin][i] > 0 ? Graph[begin][i] : INF; D[begin] = 0; int S[31*31],Q[31*31];//无所谓 int p_S=0 ,p_Q=0, len_S = 1 , len_Q = cnt-1 ; S[p_S++] = begin; for (int i = 1; i <= cnt; ++i) if( i != begin) { Q[p_Q++] = i; } while(len_Q > 1){ int u=0, minD = INF; int qid = 0; for (int i = 0; i < p_Q; ++i) if(Q[i]!=0) { if(D[Q[i]]<minD){ u = Q[i]; minD = D[u]; qid = i; } } if(u ==0 or u == end){ break; } Q[qid] = 0; len_Q--; S[p_S++] = u; len_S++; for (int i = 0; i < p_Q; ++i) if(Q[i]!=0) { int v = Q[i]; if(Graph[u][v] > 0){ if(D[v] > D[u]+Graph[u][v]) D[v] = D[u]+Graph[u][v];//更新 } } } return D[end]; } /* 4 5 1 2 1 0 1 0 1 3 0 2 0 4 0 1 2 0 0 0 0 0 1 0 1 -1 3 -1 5 6 -1 -1 -1 10 -1 12 -1 -1 -1 -1 -1 -1 19 -1 */