题目

源地址:

http://poj.org/problem?id=1979

理解

一个比较简单的DFS练习题

代码

#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>
using namespace std;
#define MAX 25

char tiles[MAX][MAX];
int used[MAX][MAX];
int count, w, h;

void dfs(int i, int j)
{
    count++;
    if (i > 1 && used[i - 1][j] == 0)
    {
        used[i - 1][j] = 1; dfs(i - 1, j);
    }
    if (i < h && used[i + 1][j] == 0)
    {
        used[i + 1][j] = 1; dfs(i + 1, j);
    }
    if (j > 0 && used[i][j - 1] == 0)
    {
        used[i][j - 1] = 1; dfs(i, j - 1);
    }
    if (j < w - 1 && used[i][j + 1] == 0)
    {
        used[i][j + 1] = 1; dfs(i, j + 1);
    }
}

int main(int argc, char const *argv[])
{
    int starti, startj;
    while (scanf("%d %d", &w, &h) && w != 0 && h != 0)
    {
        if (w == 0 || h == 0)
            break;
        count = 0;
        memset(used, 0, sizeof(used));
        for (int i = 1; i <= h; i++)
        {
            scanf("%s", tiles[i]);
        }
        for (int i = 1; i <= h; i++)
        {
            for (int j = 0; j < w; j++)
            {
                if (tiles[i][j] == '#')
                    used[i][j] = 1;
                else if (tiles[i][j] == '@')
                {
                    used[i][j] = 1;
                    startj = j;
                    starti = i;
                }
            }
        }
        dfs(starti, startj);
        printf("%d\n", count);
    }
    return 0;
}

更新日志

  • 2014年08月02日 已AC。