SCUT - 31 - 清一色

https://scut.online/p/31

还是不知道为什么RE了。的确非常玄学。

重构之后就没问题了。果然写的越复杂，分的情况越乱就越容易找不到bug。
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int cnt[15];

int cnt2[15];

bool dfs(int x, int rest, bool dui) {

    if(rest == 0)

        return true;

    if(cnt2[x] == 0)

        return dfs(x + 1, rest, dui);

    if(cnt2[x] == 1) {

        if(x <= 7 && cnt2[x + 1] >= 1 && cnt2[x + 2] >= 1) {

            cnt2[x]--, cnt2[x + 1]--, cnt2[x + 2]--;

            if(dfs(x + 1, rest - 3, dui))

                return true;

            cnt2[x + 2]++, cnt2[x + 1]++, cnt2[x]++;

        }

        return false;

    }

    if(cnt2[x] == 2) {

        if(!dui) {

            cnt2[x] -= 2;

            if(dfs(x + 1, rest - 2, true))

                return true;

            cnt2[x] += 2;

        }

        if(x <= 7 && cnt2[x + 1] >= 2 && cnt2[x + 2] >= 2) {

            cnt2[x] -= 2, cnt2[x + 1] -= 2, cnt2[x + 2] -= 2;

            if(dfs(x + 1, rest - 6, dui))

                return true;

            cnt2[x + 2] += 2, cnt2[x + 1] += 2, cnt2[x] += 2;

        }

        return false;

    }

    if(cnt2[x] >= 3) {

        if(!dui) {

            cnt2[x] -= 2;

            if(dfs(x, rest - 2, true))

                return true;

            cnt2[x] += 2;

        }

        cnt2[x] -= 3;

        if(dfs(x, rest - 3, dui))

            return true;

        cnt2[x] += 3;

        if(x <= 7 && cnt2[x + 1] >= 1 && cnt2[x + 2] >= 1) {

            cnt2[x] --, cnt2[x + 1] --, cnt2[x + 2] --;

            if(dfs(x, rest - 3, dui))

                return true;

            cnt2[x + 2] ++, cnt2[x + 1] ++, cnt2[x] ++;

        }

        return false;

    }

}

vector<int> ans;

void check(int x) {

    memcpy(cnt2, cnt, sizeof(cnt2));

    cnt2[x]++;

    if(cnt2[x] > 4)

        return;

    int cnttwo = 7;

    for(int i = 1; i <= 9; ++i)

        cnttwo -= (cnt2[i] == 2);

    if(cnttwo == 0 || dfs(1, 14, false))

        ans.push_back(x);

}

int main() {

#ifdef Yinku

    freopen("Yinku.in", "r", stdin);

#endif // Yinku

    int T;

    char s[20];

    scanf("%d", &T);

    while(T--) {

        scanf("%s", s + 1);

        memset(cnt, 0, sizeof(cnt));

        for(int i = 1; i <= 13; ++i)

            cnt[s[i] - '0']++;

        ans.clear();

        for(int i = 1; i <= 9; ++i)

            check(i);

        if(ans.empty())

            ans.push_back(-1);

        for(auto i : ans)

            printf("%d", i);

        puts("");

    }

}
巴特西

SCUT - 31 - 清一色 - dfs

最新文章

热门文章
