HDU 1312 Red and Black --- 入门搜索 BFS解法

　　HDU 1312

　　题目大意： 一个地图里面有三种元素，分别为"@"，".","#",其中@为人的起始位置，"#"可以想象为墙，然后.为可以走的空地，求人可以走的最大点数。

　　解题思路：从起点开始，起点的四个方向满足条件的点分别入队(放置重复入队，需只要一入队就标记已访问而不是取出时再进行标记)，直至队为空。

/*HDU 1312 ----- Red and Black  入门搜索 BFS解法*/

#include <cstdio>

#include <queue>

using namespace std;

int n, m; //n行m列

int cnt;

char mapp[][];

int dirx[] = { -, , ,  };

int diry[] = { , , -,  }; //用于循环来访问4个方向

struct Node{

    int x, y;

};

queue<Node> q;

void bfs(){

    /*队不为空时 表明还可以近一步搜索*/

    /*在队中的点都是已访问过、但需近一步访问周围四个方向的点的点*/

    while (!q.empty()){

        Node tmp = q.front();

        q.pop();

        Node tmp2;

        /*近一步判断该点的四个方向四否可以访问*/

        for (int i = ; i < ; ++i){

            //tmp2即为4个方向的点

            tmp2.x = tmp.x + dirx[i];

            tmp2.y = tmp.y + diry[i];

            if (tmp2.x >=  && tmp2.x < n && tmp2.y >=  && tmp2.y < m

                && mapp[tmp2.x][tmp2.y] != '#'){

                //该点可访问

                ++cnt;

                mapp[tmp2.x][tmp2.y] = '#'; //访问过后标记为不可访问

                q.push(tmp2); //入队以下次循环近一步搜索

            }

        }//for(i)

    }//while(empty)

}

int main()

{

    int startx, starty;

    //m行m列 注意题目先给出列数

    while (scanf("%d%d", &m, &n) ==  && (m + n)){

        for (int i = ; i < n; ++i){

            scanf("%s", mapp[i]);

            for (int j = ; j < m; ++j){

                if ('@' == mapp[i][j]){

                    startx = i;

                    starty = j;

                    cnt = ; //初始化找到一块

                    mapp[i][j] = '#'; //访问过后为已访问过

                }

            }

        }//for(i)

        Node start;

        start.x = startx; start.y = starty;

        q.push(start);

        bfs();

        printf("%d\n", cnt);

    }

    return ;

}

HDU 1312 Red and Black --- 入门搜索 BFS解法的相关教程结束。