POJ 1979 Red and Black 《挑战程序设计竞赛(第2版)》练习题答案 � 码农场

POJ 1979 Red and Black

There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one of four adjacent tiles. But he can't move on red tiles, he can move only on black tiles. 

Write a program to count the number of black tiles which he can reach by repeating the moves described above.

  一个房间上有红色的瓦和黑色的瓦片，给出红瓦和黑瓦的位置和人所占的位置，求人最多能走过多少片瓦？ 
（条件为：人行走过程中只能走黑瓦，且人的初始位置为黑瓦） 
输入描述：输入的字符里面只有三种字符： 
           "@"―�表示人（只能有一个该字符） 
           "."―�表示黑瓦 
           "#"―�表示红瓦 

char room[MAX_W][MAX_H];

int W, H;

const int direction[4][2] = {

    {-1, 0},

    {1, 0},

    {0, -1},

    {0, 1},

};

 

int step = 0;

 

int dfs(const int& x, const int& y)

{

    room[x][y] = '#';

    ++step;

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

    {

        int nx = x + direction[i][0];

        int ny = y + direction[i][1];

        if (nx >= 0 && nx < W && ny >= 0 && ny < H && room[nx][ny] == '.')

        {

            dfs(nx, ny);

        }

    }

 

    return step;

}

 

int main(int argc, char *argv[])

{

#ifndef ONLINE_JUDGE

    freopen("in.txt", "r", stdin);

    freopen("out.txt", "w", stdout);

#endif

    while (cin >> W >> H, W > 0)

    {

        step = 0;

        int x, y;

        for (y = 0; y < H; ++y)

        {

            for (x = 0; x < W; ++x)

            {

                cin >> room[x][y];

            }

        }

 

        bool found = false;

        for (x = 0; x < W; ++x)

        {

            for (y = 0; y < H; ++y)

            {

                if (room[x][y] == '@')

                {

                    found = true;

                    break;

                }

            }

            if (found)

            {

                break;

            }

        }

 

        cout << dfs(x, y) << endl;

    }

#ifndef ONLINE_JUDGE

    fclose(stdin);

    fclose(stdout);

    system("out.txt");

#endif

    return 0;

}

Read full article from POJ 1979 Red and Black 《挑战程序设计竞赛(第2版)》练习题答案 � 码农场