搜索加一丢丢剪枝，代码：
#include<iostream> #include<cmath> #include<queue> using namespace std; int b[110][110]; char a[110][110]; int n,m; int ans[110][110]; int jian_ji(int x,int y,int l,int r) { return abs(x-l)+abs(y-r);//剪枝 //用曼哈顿距离去估算 } int bfs(int x,int y,int l,int r) { queue<int> q1; queue<int> q2; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) ans[i][j]=0;//归零 } q1.push(x); q2.push(y); while(!q1.empty()&&!q2.empty()) { int tx=q1.front(); int ty=q2.front(); q1.pop(); q2.pop(); if(tx==l&&ty==r)//如果到当前终点 { return ans[tx][ty]; } //四个方向 if(ans[tx+1][ty]==0&&a[tx+1][ty]!='#'&&tx+1<=n) { ans[tx+1][ty]=ans[tx][ty]+1; q1.push(tx+1); q2.push(ty); } if(ans[tx-1][ty]==0&&a[tx-1][ty]!='#'&&tx-1>=1) { ans[tx-1][ty]=ans[tx][ty]+1; q1.push(tx-1); q2.push(ty); } if(ans[tx][ty+1]==0&&a[tx][ty+1]!='#'&&ty+1<=m) { ans[tx][ty+1]=ans[tx][ty]+1; q1.push(tx); q2.push(ty+1); } if(ans[tx][ty-1]==0&&a[tx][ty-1]!='#'&&ty-1>=1) { ans[tx][ty-1]=ans[tx][ty]+1; q1.push(tx); q2.push(ty-1); } } return 100001; } int main() { while(scanf("%d%d",&n,&m)&&n!=0&&m!=0) { int x1=0,y1=0,x2=0,y2=0; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>a[i][j]; if(a[i][j]=='@') { x1=i; y1=j; } if(a[i][j]=='s') { x2=i; y2=j; } } } int maxn=100001; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(a[i][j]=='*') { int y=0; y+=jian_ji(x1,y1,i,j);//从起点搜到当前的药的节点，估算 y+=jian_ji(i,j,x2,y2);//从药的节点搜到终点 if(y<maxn)//如果估算的值小于上一次的步数 { int x=0; x+=bfs(x1,y1,i,j);//和上面一样 x+=bfs(i,j,x2,y2); if(maxn>x) { maxn=x; } } } } } if(maxn==100001) cout<<"-1"<<endl; else cout<<maxn<<endl; } }