POJ_1979

题目描述：

　　每组数据给你一张字符的图，'@'代表起点，'.'代表可走的路，'#'代表墙，求从起点出发，可到达的位置的数量，包括起点。

思路：

　　dfs基础题，从起始点开始，每一次所在的点，只要不出界并且字符为'@'或'.'，则把这个点的字符改为一个标志，再向四周扩散。如果出了边界或者遇到'#',则这条路到尽头。

　　最后只要遍历整张图，统计标志的数量即可。

　　好像有点不道德，直接把原图修改了= =

#include<iostream>

#include<cstdio>

#include<string>

using namespace std;

string a[];

int H,W,dir[][] ={{,-},{,},{,},{-,}};

void dfs(int x,int y)

{

    if(x <  || x >= H || y <  || y >= W)  return;

    if(a[x][y] == '.' || a[x][y] == '@')

    {

        a[x][y] = '';

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

        {

            int xx = x+dir[i][],yy = y+dir[i][];

            dfs(xx,yy);

        }

    }

}

int main()

{

    while(cin >> W >> H && W && H)

    {

        int beginx,beginy;

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

        {

            cin >> a[i];

        }

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

        {

            for(int j = ;j < W;j++)

            {

                if(a[i][j] == '@')

                {

                    beginx = i;

                    beginy = j;

                }

            }

        }

        dfs(beginx,beginy);

        int sum = ;

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

        {

            for(int j = ;j < W;j++)

            {

                if(a[i][j] == '')    sum++;

            }

        }

        cout << sum << endl;

    }

    return ;

}

巴特西

POJ_1979_dfs

最新文章

热门文章