竞赛讨论区 > 为什么我B题会WA
头像
hulean
发布于 2020-09-14 20:53
+ 关注

为什么我B题会WA

#include<bits/stdc++.h>
using namespace std;
const int N = 3000 + 5;
int n, m;
int dx[5] = {0, 1, -1, 0, 0}, dy[5] = {0, 0, 0, -1, 1};
bool Map[N][N], vis[N][N], in[N][N];
int maxx, maxtmp;
struct Node{
    int x, y;
};
inline int add (int x, int y) {
    memset (in, 0, sizeof (in));
    int res = 0;
    queue< Node >q;
    q.push((Node){x, y}); in[x][y] = 1;
    while (q.size ()) {
        Node now = q.front ();
        q.pop ();
        for (int i = 1; i <= 4; i++) {
            int a = now.x + dx[i], b = now.y + dy[i];
            if (Map[a][b] == 0 || a < 1 || b < 1 || a > n || b > m) res ++;
            if (a < 1 || b < 1 || a > n || b > m || in[a][b] || Map[a][b] == 0) continue;
            in[a][b] = 1;
            q.push((Node){a, b});
        }
    }
    return res;
}
inline void bfs (int x, int y) {
    int stp = 0;
    queue< Node >q;
    q.push((Node){x, y}); vis[x][y] = 1;
    while (q.size ()) {
        Node now = q.front ();
        q.pop ();
        stp++;
        for (int i = 1; i <= 4; i++) {
            int a = now.x + dx[i], b = now.y + dy[i];
            if (a < 1 || b < 1 || a > n || b > m || vis[a][b] || Map[a][b] == 0) continue;
            vis[a][b] = 1;
            q.push((Node){a, b});
        }
    }
    if (stp >= maxx) {
        int tmp = add(x, y);
        // cout<<tmp<<endl;
        if (maxx == 0) maxx = stp, maxtmp = tmp;
        else if (stp > maxx) maxx = stp, maxtmp = tmp;
        else if (tmp < maxtmp) maxtmp = tmp;
    }
}
signed main () {
    char ch;
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) cin>>ch, Map[i][j] = ch - '0';
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++)
            if (vis[i][j] == 0 && Map[i][j] == 1) bfs(i, j);
    }
    // printf ("%d\n", maxx);
    if (maxx == 0 ) printf ("What a pity!\n");
    else printf ("%d\n", maxtmp);
    return 0;
}

核心思想:找bfs找连通块,与最大的进行比较,并且计算外围周长,更新答案

不知道有什么问题,谜之WA

全部评论

(3) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐