作者: JeremyChan | 来源:发表于2017-03-14 21:40 被阅读52次

    POJ-1979 Red and Black

    Q: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.
    
    #include<iostream>
    #include <stdlib.h>
    #define MAX_NUM 21
    using namespace std;
    
    int dire[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };   //分别定义四个方向
    int DFS(char arr[][MAX_NUM], int start_x, int start_y, int H, int W) {
        if (arr[start_x][start_y] == '#'|| start_x >= W || start_y >= H || start_x < 0 || start_y < 0)   //退出条件
        {
            return 0;
        }
        int res = 1;
        arr[start_x][start_y] = '#';    //遍历以后进行标记,防止重复计数
        for (int i = 0; i < 4; i++)
        {
            res += DFS(arr, start_x + dire[i][0], start_y + dire[i][1], H, W);
        }
        return res;
    }
    
    int main()
    {
        char arr[MAX_NUM][MAX_NUM];
        memset(arr, 0, sizeof(arr));
        int H, W, start_x, start_y;
        while (cin >> H >> W&&(H != 0&&W != 0)) {
            for (int i = 0; i < W; i++)
            {
                for (int j = 0; j < H; j++)
                {
                    cin >> arr[i][j];
                    if (arr[i][j] == '@')
                    {
                        start_x = i;
                        start_y = j;
                    }
                }
            }
            int res = DFS(arr, start_x, start_y, H, W);
            cout << res << endl;
        }
        return 0;
    }
    

    相关文章

      网友评论

          本文标题:

          本文链接:https://www.haomeiwen.com/subject/awkknttx.html