《算法竞赛从入门到进阶》第四章 搜索技术 hdu1312 "Red and Black" BFS

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
char room[25][25];
int dir[4][2]={{-1,0},{0,-1},{1,0},{0,1}};
int Wx,Hy,num;
//Wx,Hy:长宽的边界 ，num:从初始瓷砖到能到达的瓷砖的总数 
#define CHECK(x,y) (x<Wx&&x>=0&&y>=0&&y<Hy) 
//检查是否越界 
struct node
{
    int x,y; 
};
void BFS(int dx,int dy)
{
    queue<node> q;
    node start,next;
    start.x = dx;
    start.y = dy;
    q.push(start);//把当前节点入队
    while(!q.empty())
    {
        start = q.front();
        q.pop();
        for(int i=0;i<4;++i)
        {
            next.x=start.x+dir[i][0];
            next.y=start.y+dir[i][1];
            if(CHECK(next.x,next.y)&&room[next.x][next.y]==‘.‘)
            {
                room[next.x][next.y]=‘#‘;//标记一下当前节点已经走过了 
                num++;//步数自增 
                q.push(next);//将子节点入队 
            }
        }
    } 
}
int main()
{
    int x,y,dx,dy; 
    //dx,dy： 人的站位 
    while(cin>>Wx>>Hy)
    {
        if(Wx==0&&Hy==0)
        {
            break;
        }
        for(y=0;y<Hy;++y)
        {
            for(x=0;x<Wx;++x)
            {
                cin>>room[x][y];
                if(room[x][y]==‘@‘)
                {
                    dx=x;
                    dy=y; 
                } 
            }
        }
        
        num=1;
        BFS(dx,dy);
        cout<<num<<endl;
    }
    return 0;
 } 

#include<iostream>
#include<string.h>
#include<queue> 
using namespace std;
int to[2]={1,-1};
int a,b,sum;
int vis[100000];
struct place
{
    int x,time;
};
int check(place k)
{
    if(k.x<0||k.x>100000||vis[k.x]==1)
        return 0;
    return 1;
}
int bfs(place n)
{
    place m,next;
    queue<place>w;
    w.push(n);
    while(!w.empty())
    {
        m=w.front();
        w.pop();
        if(m.x==b)
            return m.time;
        for(int i=0;i<2;i++)
        {
            next.x=m.x+to[i];
            next.time=m.time+1;
            if(next.x==b)
                return next.time;
            if(check(next))
            {
                w.push(next);
                vis[next.x]=1;
            }
        }
        next.x=m.x*2;
        next.time=m.time+1;
        if(next.x==b)
            return next.time;
        if(check(next))
        {
            w.push(next);
            vis[next.x]=1;
        }
    }
    return 0;
}
int main()
{
    int i,j,t;
    place x1;
    while(~scanf("%d %d",&a,&b))
    {
        x1.x=a;
        x1.time=0;
        vis[x1.x]=1;
        sum=0;
        sum=bfs(x1);
        printf("%d\n",sum);
    }
    return 0;
}