POJ-1979 Red and Black

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;
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容