bfs开始的基础学习

//要用队列
1.学bfs的开始
油田问题
http://acm.hdu.edu.cn/showproblem.php?pid=1241
//其实dfs可以的，bfs也可以写，正好学习一下bfs的写法
//抄的别人的···········//应该比较好理解

#include<bits/stdc++.h>
using namespace std;
int dir[][2]= {0,1,0,-1,1,0,-1,0,1,1,-1,1,1,-1,-1,-1};
int m,n;
char mapa[105][105];
struct node
{
    int x,y;
} now,nex;
void bfs(int x,int y)
{
    now.x=x,now.y=y;
    queue<node>Q;
    Q.push(now);
    mapa[x][y]='*';
    while(!Q.empty())
    {
        now=Q.front();
        Q.pop();
        for(int i=0; i<8; ++i)
        {
            int xx=dir[i][0]+now.x;
            int yy=dir[i][1]+now.y;
            if(xx < 0||xx >= m||yy < 0||yy >= n)
                continue;
            if(mapa[xx][yy]=='*')
                continue;
            mapa[xx][yy]='*';
            //now.x=xx,now.y=yy;
            nex.x=xx;
            nex.y=yy;
            Q.push(nex);
        }

    }
}

int main()
{

    while(scanf("%d %d",&m,&n)!=EOF)
    {
        int res=0;
        if(n==0&&m==0)
            break;
        for(int i=0; i<m; ++i)
            scanf("%s",mapa[i]);
        for(int i=0; i<m; ++i)
            for(int j=0; j<n; ++j)
            {
                if(mapa[i][j]=='@')
                {
                    ++res;
                    bfs(i,j);
                }
            }
        printf("%d\n",res);
    }
    return 0;

}

2.经典迷宫问题
http://www.acmicpc.sdnu.edu.cn/problem/show/1086
路径标记求最短路径+标记
hhhh其实是基础的bfs
hhhhhh理解了半天
感谢zbl兄弟

#include<bits/stdc++.h>
using namespace std;
int Move[][2]= {0,1,0,-1,1,0,-1,0};
int maze[10][10];
int a[30],b[30];
int m,n,res;
struct Node
{
    int x,y,step;//横纵坐标，步数
    int moves[30];记录行动轨迹
} fr,ne;//上一步和下一步的行动情况
void bfs()
{
    fr.x=0;
    fr.y=0;
    fr.step=0;
    queue<Node>Q;
    Q.push(fr);
    while(!Q.empty())
    {
        fr=Q.front();//要记住Q.front()是哪个然后还有Q.front的fr.step是多少，要不就很容易弄错hhhh//循环时一定要注意fr，ne的值分别为多少，要不根本得不出正确答案hhhh
        Q.pop();
        if(fr.x == 4&&fr.y == 4)
            break;//如果走到迷宫出口//结束，bfs搜索到了出口，即为最短路径//开始输出
        for(int i = 0; i < 4; ++i)
        {
            ne = fr;//这个是要存储moves数组的//即继承之前的运动轨迹
            ne.x =fr.x + Move[i][0];
            ne.y =fr.y + Move[i][1];
            ne.step = fr.step + 1;
            ne.moves[fr.step] = i;//用这一个来记录走这条路径的下一个方向
            if(ne.x >= 0&&ne.x < 5&&ne.y >= 0&&ne.y < 5&&!maze[ne.x][ne.y])
            {
                Q.push(ne);//如果满足条件入队列，记录这条路径的方向//然后接着循环是如果满足条件再进队列记录的是搜索出来的另一个路径再进队列
            }
        }
    }
    int x = 0,y = 0;
    for(int i = 0; i < fr.step; ++i)
    {
        printf("(%d, %d)\n",x,y);
        x = x + Move[fr.moves[i]][0];
        y = y + Move[fr.moves[i]][1];//一个个相加记录值

    }
    printf("(%d, %d)\n",x,y);



}
int main()
{
    for(int i=0; i<5; ++i)
        for(int j=0; j<5; ++j)
            scanf("%d",&maze[i][j]);
    bfs();
    return 0;
}