帮忙debug一下K题QWQ

debug死了.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define endt ' '
#define pll pair<ll, ll>
#define lowbit(emm) (emm & (-emm))
const int inf = 2147483647;
vector<ll> ufs(250010);
vector<vector<ll>> cnt(250010);
ll find(ll x)
{
    if (x != ufs[x])
    {
        ll t = find(ufs[x]);
        ufs[x] = t;
    }
    return ufs[x];
}
void join(ll x, ll y)
{
    ll rx = find(x);
    ll ry = find(y);
    if (rx != ry)
    {
        ufs[y] = x;
    }
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    ll n, m;
    cin >> n >> m;
    vector<ll> a(n * m + 10);
    for (ll i = 1; i <= n * m; i++)
    {
        ufs[i] = i;
    }
    for (ll i = 1; i <= n * m; i++)
    {
        char s;
        cin >> s;
        a[i] = s - '0';
    }
    for (ll i = 1; i <= n * m; i++)
    {
        if (a[i] == 1)
        {
            if (i - 1 > 0 && (i - 1) % m != 0)
            {
                if (a[i - 1] == 0)
                {
                    cnt[i].push_back(i - 1);
                }
                else
                {
                    join(i, i - 1);
                }
            }
            if (i - m > 0)
            {

                if (a[i - m] == 0)
                {
                    cnt[i].push_back(i - m);
                }
                else
                {
                    join(i, i - m);
                }
            }
            if (i + 1 < n * m + 1 && (i + 1) % m != 1)
            {
                if (a[i + 1] == 0)
                {
                    cnt[i].push_back(i + 1);
                }
                else
                {
                    join(i, i + 1);
                }
            }
            if (i + m < n * m + 1)
            {
                if (a[i + m] == 0)
                {
                    cnt[i].push_back(i + m);
                }
                else
                {
                    join(i, i + m);
                }
            }
        }
    }
    for (ll i = 1; i <= n * m; i++)
    {
        if (ufs[i] != i)
        {
            ll len = cnt[i].size();
            for (ll j = 0; j < len; j++)
            {
                cnt[find(i)].push_back(cnt[i][j]);
            }
        }
    }
    ll minn = 1e10;
    for (ll i = 1; i <= n * m; i++)
    {
        if (ufs[i] == i&&a[i]==1)
        {
            sort(cnt[i].begin(),cnt[i].end());
            cnt[i].erase(unique(cnt[i].begin(), cnt[i].end()), cnt[i].end());
            ll len = cnt[i].size();
            minn=min(len,minn);
        }
    }
    cout << minn;
    return 0;
}

全部评论
7 7 1111111 0111111 1111111 1111111 0111111 0111111 1111111
点赞 回复 分享
发布于 01-23 20:37 福建

相关推荐

07-14 13:47
门头沟学院 Java
Lynn012:你评估好自己的位置了吗《顶尖应届》
投递小米集团等公司7个岗位
点赞 评论 收藏
分享
07-15 11:41
门头沟学院 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务