wikioi 2074 营救 - c++编程基础

分析：

比较典型的宽搜。

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

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

代码：

#include  
#include  
#include  
#include  
#include  
#define nn 501  
using namespace std;  
queue  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])