wikioi 2074 营救

分析：

比较典型的宽搜。

开队列记录状态，另外开数组记录力气和步数，每扩展到一个点，先判断是否越界，再判断搜到的值是否小于当前最优值，如果符合要求，入队。

注意结构体中的变量不要开得太多，否则会超时。

代码：

#include<iostream>  
#include<cstdio>  
#include<cmath>  
#include<ctime>  
#include<queue>  
#define nn 501  
using 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";  //无解的情况  
   else cout<<b1[x2][y2]<<" "<<b[x2][y2];  
}

补充：软件开发 , C++ ,