专栏首页机器学习与自然语言处理POJ-1979 Red and Black(DFS)

POJ-1979 Red and Black(DFS)

题目链接:http://poj.org/problem?id=1979

深度优先搜索非递归写法

#include <cstdio>
#include <stack>

using namespace std;
const int MAX_W = 25, MAX_H = 25;
char Map[MAX_W][MAX_H+1];
int W, H;

int DFS(int sx, int sy);

int main()
{
    while (scanf("%d %d", &H, &W) == 2
           && W != 0 && H != 0) {
        for (int i = 0; i < W; i++)
            scanf("%s", Map[i]);
        for (int i = 0; i < W; i++)
            for (int j = 0; j < H; j++) {
                if (Map[i][j] == '@')
                    printf("%d\n", DFS(i, j));
            }
    }
    return 0;
}

int DFS(int sx, int sy)
{
    int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
    int Visited[MAX_W][MAX_H] = {0};
    typedef pair<int, int> Position;
    stack<Position> sta;

    Visited[sx][sy] = 1;
    int num = 1;
    Map[sx][sy] = '.';
    sta.push(Position(sx, sy));

    while (!sta.empty()) {
        Position p = sta.top(); sta.pop();
        for (int i = 0; i < 4; i++) {
            int nx = p.first + dx[i], ny = p.second + dy[i];
            if (0 <= nx && nx < W && 0 <= ny && ny < H &&
                Map[nx][ny] == '.' && !Visited[nx][ny]) {
                sta.push(Position(nx, ny));
                Visited[nx][ny] = 1;
                num++;
            }
        }
    }
    return num;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 04-树6. Huffman Codes--优先队列(堆)在哈夫曼树与哈夫曼编码上的应用

    题目来源:http://www.patest.cn/contests/mooc-ds/04-%E6%A0%916 In 1953, David A. Huffm...

    llhthinker
  • Lake Counting(POJ-2386)

    题目链接: http://poj.org/problem?id=2386 题目大意: 计算出相连的'W'有多少块 所需算法: 深度优先搜索(DFS) 主要思路:...

    llhthinker
  • 深度优先生成树及其应用

    在上一篇博客判断有向图是否有圈中从递归的角度简单感性的介绍了如何修改深度优先搜索来判断一个有向图是否有圈。事实上, 它的实质是利用了深度优先生成树(depth-...

    llhthinker
  • 2-Sat+输出可行解(个人模版)

    2-Sat+输出可行解: 1 //LightOJ 1251 2 #include<stdio.h> 3 #include<string.h> 4...

    Angel_Kitty
  • BZOJ4810: [Ynoi2017]由乃的玉米田(莫队+bitset)

    Description 由乃在自己的农田边散步,她突然发现田里的一排玉米非常的不美。这排玉米一共有N株,它们的高度参差不齐。 由乃认为玉米田不美,所以她决定出...

    attack
  • BZOJ2595: [Wc2008]游览计划(斯坦纳树,状压DP)

    attack
  • Kolakoski序列产生器

    xiaoxi666
  • 【CodeForces 620D】Professor GukiZ and Two Arrays

    两个数列,一个有n个数,另一个有m个数,让你最多交换两次两个数列的数,使得两个数列和的差的绝对值最小,求这个差的绝对值、最少交换次数、交换数对

    饶文津
  • 「2017 Multi-University Training Contest 2」2017多校训练2

    给定数组a[1..n]和b[1..n],b[i]在[1~n]内。要得到a[n+1..2n],每次选b数组的一个,令a[i]为j=b[k]到i-1位置中最大的a[...

    饶文津
  • P1903 【模板】分块/带修改莫队(数颜色)

    题目描述 墨墨购买了一套N支彩色画笔(其中有些颜色可能相同),摆成一排,你需要回答墨墨的提问。墨墨会像你发布如下指令: 1、 Q L R代表询问你从第L支画笔到...

    attack

扫码关注云+社区

领取腾讯云代金券