AcWing 1113. 红与黑

1、题目描述

有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。

你站在其中一块黑色的瓷砖上，只能向相邻（上下左右四个方向）的黑色瓷砖移动。

请写一个程序，计算你总共能够到达多少块黑色的瓷砖。

输入格式

输入包括多个数据集合。

每个数据集合的第一行是两个整数 W 和 H，分别表示 x 方向和 y 方向瓷砖的数量。

在接下来的 H 行中，每行包括 W 个字符。每个字符表示一块瓷砖的颜色，规则如下

1）‘.’：黑色的瓷砖；

2）‘#’：红色的瓷砖；

3）‘@’：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。

当在一行中读入的是两个零时，表示输入结束。

输出格式

对每个数据集合，分别输出一行，显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。

数据范围

1≤W,H≤20

输入样例：

6 9

....#.

.....#

......

......

......

......

......

#@...#

.#..#.

0 0

输出样例：

2、算法描述

本题考察的是Flood fill算法（洪水泛滥算法）、可以借助DFS、BFS两种方式来实现、经典的走迷宫问题、并且可以扩展维度、这里是上下左右四个方向、经常使用到的坐标板子如下所示。

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

即借助DFS、BFS两种方式、都能解决此类问题、并且套路固定、下面是做法。

1、DFS

#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

using namespace std;

const int N = 25;

char g[N][N];

int n, m;

bool st[N][N];  // 状态数组

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0 , -1};  // 坐标

int dfs(int x, int y)

{

    int cnt = 1;    // 自己从第一块砖出发

    st[x][y] = true;

    for(int i = 0 ; i < 4 ; i ++)   // 四个方向

    {

        int a = x + dx[i], b = y + dy[i];

        if(a < 0 || a >= n || b < 0 || b >= m) continue;    // 越界

        if(g[a][b] == '#') continue;    // 踩到红砖

        if(st[a][b]) continue;  // 已经踩过

        cnt += dfs(a, b);   // 递归、层级灌溉

    }

    return cnt;

}

int main()

{

    while(cin >> m >> n, m || n)

    {

        for(int i = 0 ; i < n ; i ++) cin >> g[i];

        int x, y;

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

            for(int j = 0 ; j < m ; j ++ )

                if(g[i][j] == '@')

                {

                    x = i;

                    y = j;

                }

        memset(st, 0, sizeof st);   // 每轮都要清空状态

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

    }

    return 0;

}

2、BFS

#include <iostream>

#include <cstring>

#include <algorithm>

#include <queue>    // BFS需要借助队列

#define x first

#define y second

using namespace std;

typedef pair<int, int> PII; // 涉及到坐标用pair

const int N = 25;

char g[N][N];

int m, n;

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int bfs(int sx, int sy)

{

    queue<PII> q;

    q.push({sx, sy});

    //g[sx][sy] = '#';    // 当前踩的点标记

    int res = 0;

    while(q.size())

    {

        auto t = q.front(); // 获取队头元素

        q.pop();    // 弹出队头元素

        res ++ ;

        for(int i = 0 ; i < 4 ; i ++)   // 拓展四个方向

        {

            int x = t.x + dx[i], y = t.y + dy[i];

            if(x < 0 || x >= n || y < 0 || y >= m || g[x][y] != '.') continue;  // 越界情况

            g[x][y] = '#';  // 踩过之后标记

            q.push({x, y}); // 放入队列

        }

    }

    return res;

}

巴特西

AcWing 1113. 红与黑

1、题目描述

2、算法描述

1、DFS

2、BFS

最新文章

热门文章