题目描述

1213 农夫约翰有一片 N∗M 的矩形土地。

最近，由于降雨的原因，部分土地被水淹没了。

现在用一个字符矩阵来表示他的土地。

每个单元格内，如果包含雨水，则用”W”表示，如果不含雨水，则用”.”表示。

现在，约翰想知道他的土地中形成了多少片池塘。

每组相连的积水单元格集合可以看作是一片池塘。

每个单元格视为与其上、下、左、右、左上、右上、左下、右下八个邻近单元格相连。

请你输出共有多少片池塘，即矩阵中共有多少片相连的”W”块。

输入样例

10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

输出样例

3

求解思路

第一步：找到一个W方块
第二步：遍历这个W方块的四周，把和这个方块有联系的全部都标记上
第三步：找下一个没有被标记的，重复一二步

BFS

(肯定不超过n^3！)

C++ 代码

#include <cstring>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>

using namespace std;
typedef pair<int, int> PII;
queue<PII> q;
const int N = 1050;
char map[N][N];
bool st[N][N];
int n, m;
int ans;

void bfs(int sx, int sy) {
    int dx[] = { -1,-1,0,1,1,1,0,-1 };
    int dy[] = { 0,1,1,1,0,-1,-1,-1 };
    //坐标偏移量是从0点方向，顺时针写下来的。
    q.push({ sx,sy });
    while (!q.empty())
    {
        PII t = q.front();
        q.pop();
        for (int i = 0; i < 8; i++)
        {
            int a = t.first + dx[i];
            int b = t.second + dy[i];

            if (a < 0 || b < 0 || a >= n || b >= m) continue;//越界
            if (map[a][b] == '.') continue;//走不了
            if (st[a][b]) continue;//之前走过

            st[a][b] = true;
            q.push({ a,b });
        }
    }
}


int main() {

    scanf("%d %d", &n, &m);

    for (int i = 0; i < n; i++)
        scanf("%s", map[i]);

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {

            if (map[i][j] == 'W' && !st[i][j])
            {   
                st[i][j] = true;
                bfs(i, j);
                ans++;
            }
        }
    }

    printf("%d", ans);

}

DFS

时间复杂度 (肯定不超过n^3！)

被注释掉的部分是 BFS写法，方便对比就没有删掉
main函数部分与bfs相同，只有dfs里面的内容重新写了
另外，这个题是不用回溯的，因为整个图走一边答案就能出来

#include <cstring>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
typedef pair<int, int> PII;
queue<PII> q;
const int N = 1050;
char map[N][N];
bool st[N][N];
int n, m;
int ans;

void dfs(int sx, int sy) {
    int dx[] = { -1,-1,0,1,1,1,0,-1 };
    int dy[] = { 0,1,1,1,0,-1,-1,-1 };

    /*q.push({ sx,sy });
    while (!q.empty())
    {
        PII t = q.front();
        q.pop();
        for (int i = 0; i < 8; i++)
        {
            int a = t.first + dx[i];
            int b = t.second + dy[i];

            if (a < 0 || b < 0 || a >= n || b >= m) continue;
            if (map[a][b] == '.') continue;
            if (st[a][b]) continue;

            st[a][b] = true;
            q.push({ a,b });
        }
    }*/

    for (int i = 0; i < 8; i++)
    {
        int a = sx+dx[i];
        int b = sy + dy[i];

        if (a < 0 || b < 0 || a >= n || b >= m) continue;
        if (map[a][b] == '.') continue;
        if (st[a][b]) continue;

        st[a][b] = true;
        dfs(a, b);

    }
}


int main() {

    scanf("%d %d", &n, &m);

    for (int i = 0; i < n; i++)
        scanf("%s", map[i]);

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {

            if (map[i][j] == 'W' && !st[i][j])
            {
                st[i][j] = true;
                dfs(i, j);
                ans++;
            }
        }
    }

    printf("%d", ans);

}