【BFS】wikioi 2074 营救
题目链接：http://wikioi.com/problem/2074/
分析：
比较典型的宽搜。
开队列记录状态，另外开数组记录力气和步数，每扩展到一个点，先判断是否越界，再判断搜到的值是否小于当前最优值，如果符合要求，入队。
注意结构体中的变量不要开得太多，否则会超时。
代码：
#include<iostream>#include<cstdio>#include<cmath>#include<ctime>#include<queue>#define nn 501using namespace std;queue <int> qx,qy;int dx[8]={0,1,1,-1,0,1,-1,-1}, dy[8]={1,0,1,0,-1,-1,-1,1}; //8个方向int a[nn][nn],b[nn][nn],b1[nn][nn]={0},n,m,x,y,x1,x2,y11,y2;int main(){ freopen("1.txt","r",stdin);//freopen("2.txt","w",stdout);cin>>n>>m;cin>>x1>>y11>>x2>>y2;for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) { char ch; cin>>ch; a[i][j]=ch-'0'; b[i][j]=10000000; } int he,ta;he=1;ta=1;qx.push(x1),qy.push(y11),b1[x1][y11]=1,b[x1][y11]=0; while (!qx.empty()) { x=qx.front();y=qy.front(); for (int i=0;i<8;i++) { int xx=x+dx[i]; int yy=y+dy[i]; if (xx>0&&xx<=n&&yy>0&&yy<=m) if (a[xx][yy]!=0) if (b[x][y]+abs(a[xx][yy]-a[x][y])<b[xx][yy]|| //判断是否可行 (b[x][y]+abs(a[xx][yy]-a[x][y])==b[xx][yy]&&b1[x][y]+1<b1[xx][yy])) { qx.push(xx); qy.push(yy); b[xx][yy]=b[x][y]+abs(a[xx][yy]-a[x][y]); b1[xx][yy]=b1[x][y]+1;} } qx.pop();qy.pop(); } if (b[x2][y2]==10000000) cout<<"0 0"; //无解的情况 elsecout<<b1[x2][y2]<<" "<<b[x2][y2];}