求助dfs题关于求周长
查看原帖
求助dfs题关于求周长
593753
LukeSu楼主2022/3/10 23:57

不知道代码哪里出问题了,周长总是和正确结果差一点点。

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1006;
char g[maxn][maxn];
bool st[maxn][maxn];    //记录状态 
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
int cnt = 1;    //用来求每个连通块包含'#'数量
int N;
int length = 0;  //算周长

void dfs(int x, int y) {
    st[x][y] = true;
    for (int k = 0; k < 4; k++) {
        int X = dx[k] + x;
        int Y = dy[k] + y;
        if (g[X][Y] == '.' and !st[X][Y]) {
            ++length;   //上下左右有一个'.',那么连通块数量加1 
        }
    }
    for (int i = 0; i < 4; i++) {
        int xx = dx[i] + x;
        int yy = dy[i] + y;
        if (!st[xx][yy] and g[xx][yy] == '#' and xx >= 1 and yy >= 1 and
            xx <= N and yy <= N) {
            ++cnt;  //连通块'#'数量加1 
            dfs(xx, yy);
        }
    }
}

int main() {
    cin >> N;
    for (int i = 0; i <= N + 1; i++)
        for (int j = 0; j <= N + 1; j++) {
            g[i][j] = '.';
        }

    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            cin >> g[i][j];

    int maxcnt = 0; //求最大连通块包含'#'个数 
    int maxlength = 0; //求最大周长
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            if (g[i][j] == '#') {
                dfs(i, j);
                if (cnt > maxcnt) {
                    maxcnt = max(maxcnt, cnt);  //得到最大冰激凌球面积 
                    maxlength = max(maxlength, length); //得到最大冰激凌球周长 
                    cnt = 1;    //重置 
                    length = 0;     //重置 
                }
            }

    cout << maxcnt << " " << maxlength;

    return 0;
}
2022/3/10 23:57
加载中...