计蒜客——乳草的侵占（BFS）

BFS一直写不会，可能是多加了个队列，写起来不是太容易。不过最近还是稍微入门了BFS，跟DFS差别不太大，还是由三个部分组成——出口、标记、枚举。
DFS的主要的思想就是一条路走到黑。例如：有N个阶段，第N个阶段走不通，就返回第N-1个阶段尝试其他的可能。
而BFS维护的是一种层次关系，按照状态的层次扩展，每次离根节点越近的越先扩展。
所以，当要求最短路时，可以考虑用BFS（当然DFS在数据范围比较小的时候也OK），要求所有符合条件的情况时，考虑用DFS
下面看这道题（题目很恶心，我发现了第一个坑，但是还有第二个…）

这道题第一个坑：读入数据是行是倒着读入，列是正着读入…
我一开始写的是直接return step；得到的答案是8，明显不对。问了大佬才知道BFS并不像DFS那样：DFS每次执行都是保存着自己的答案，但是BFS在每次扩展都会有新的答案，我的写法最后返回的step，是在上一个状态基础上返回的，并不是最后一个状态的step。BFS求最短路，就是返回队列为空时最后状态的那个答案！然后我又加了个结构体成员，并且用ans记录每个状态的答案，这样的话每个状态下的ans都会更新，当队列为空时，ans保留的就是最后一次扩展的答案了。

过了样例，但是提交时候WA了，找了好久，原因是它搜索的起点也是倒着读进来的（崩溃！）…

直接放代码了：

#include <bits/stdc++.h>

using namespace std;

char mp[105][105];
bool vis[105][105];
int x,y,mx,my;
int ans;
int dir[8][2]={-1,0,-1,-1,0,-1,1,-1,1,0,1,1,0,1,-1,1};
struct node
{
    int x;
    int y;
    int d;
    node(int xx,int yy,int dd)
    {
        x=xx;
        y=yy;
        d=dd;
    }
};
bool in(int n,int m)
{
    return n>=1&&n<=x&&m>=1&&m<=y;
}

queue<node> q;
void bfs(int ux,int uy,int step)
{
    q.push(node(ux,uy,0));
    vis[ux][uy]=true;
    while(!q.empty())
    {

        node a=q.front();
        ans=a.d;//记录每个状态的步数 当BFS结束后就是最后一个状态的步数
        q.pop();
        for(int i=0;i<8;i++)
        {
            int tx=a.x+dir[i][0];
            int ty=a.y+dir[i][1];
            if(in(tx,ty)&&!vis[tx][ty]&&mp[tx][ty]=='.')
            {
                vis[tx][ty]=true;
                q.push(node(tx,ty,a.d+1));
            }
        }
    }
    //return step; //不能在最后直接返回step 因为bfs每一次扩展都会得到一个新的状态 这里返回的step是在前一个状态的基础上加过来的
    return ;
}


int main()
{
    scanf("%d%d%d%d",&y,&x,&mx,&my);
    for(int i=x;i>=1;i--)
    {
        for(int j=1;j<=y;j++)
        {
            cin>>mp[i][j];
            if(mp[i][j]=='*')
            {
                vis[i][j]=true;
            }
        }
    }
    //bfs(mx,my,0);
    bfs(my,mx,0);
    printf("%d\n",ans);
    return 0;
}

继续肝…离比赛最后一周，总结总结