[2784] 가로 세로 퍼즐

https://www.acmicpc.net/problem/2784

2784번: 가로 세로 퍼즐

디스크립션의 처음 부분이 무슨 뜻인지는 잘 모르겠지만, 어쨋든 길이3의 문자열 6개가 들어오고,

3*3의 공간에 알파벳을 배치한 후 왼쪽과 위에서 3글자씩 읽었을때 생긴 6개의 문자열이 동일한 경우를 찾는다.

여러개가 나올경우 왼쪽위부터 오른쪽 아래로 읽은 길이9의 문자열을 사전순 비교했을때 가장 앞에오는 경우가 답이다.

 

초기에 입력된 6개의 문자열중 3개만 모든 경우로 배치한 후를 생각해보면,

이미 3*3의 공간이 전부 채워졌으므로 선택되지 않은 3개의 문자열이 자동적으로 만들어졌는지만 판별하면 된다.

결국 경우의 수는 많아봤자 6! -> 브루트포스하게 찾아보자

---

#include <bits/stdc++.h>

using namespace std;

#ifdef ONLINE_JUDGE

constexpr bool local = false;

#else

constexpr bool local = true;

#endif

using ll = long long;

using pi = pair<ll, ll>;

vector<string> v, ans;

int main(void) {

    if (!local) ios_base::sync_with_stdio(0), cin.tie(0);

    int i, j;

    v.resize(6);

    for (i = 0; i < 6; i++) cin >> v[i];

    vector<int> base;

    for (i = 0; i < 6; i++) base.push_back(i);

    sort(v.begin(), v.end());

    do {

        char a[3][3];

        for (i = 0; i < 6; i++) {

            if (base[i] >= 3) continue;

            int idx = base[i];

            for (j = 0; j < 3; j++) a[idx][j] = v[i][j];

        }

        vector<string> cmp;

        for (i = 0; i < 3; i++) {

            string row = "";

            for (j = 0; j < 3; j++) row.push_back(a[i][j]);

            cmp.push_back(row);

        }

        for (j = 0; j < 3; j++) {

            string col = "";

            for (i = 0; i < 3; i++) col.push_back(a[i][j]);

            cmp.push_back(col);

        }

        sort(cmp.begin(), cmp.end());

        if (cmp == v) {

            string cur = "";

            for (i = 0; i < 3; i++)

                for (j = 0; j < 3; j++) cur.push_back(a[i][j]);

            ans.push_back(cur);

        }

    } while (next_permutation(base.begin(), base.end()) == true);

    if (ans.empty()) {

        cout << 0;

        return 0;

    }

    sort(ans.begin(), ans.end());

    for (i = 0; i < 3; i++) {

        for (j = 0; j < 3; j++) cout << ans.front()[3 * i + j];

        cout << '\n';

    }

    return 0;

}

---