結果

問題 No.3558 Dominoes, Black and White
コンテスト
ユーザー みうね
提出日時 2026-05-24 16:02:38
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
MLE  
実行時間 -
コード長 1,554 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,758 ms
コンパイル使用メモリ 348,984 KB
実行使用メモリ 1,307,328 KB
最終ジャッジ日時 2026-05-29 18:34:29
合計ジャッジ時間 13,468 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge3_0
このコードへのチャレンジ
（要ログイン）
サブタスク 配点 結果
部分点 10 % AC * 30
満点 90 % AC * 31 MLE * 2 -- * 56
合計 10 点
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

int main() {
    ll N;
    cin >> N;
    vector<string> S(N);
    for (ll i = 0; i < N; ++i) {
        cin >> S[i];
    }

    string start_S = "";
    for (ll i = 0; i < N; ++i) {
        start_S += S[i];
    }

    string goal_S = "";
    for (ll i = 0; i < N; ++i) {
        for (ll j = 0; j < N; ++j) goal_S += '.';
        for (ll j = 0; j < N; ++j) goal_S += '#';
    }

    map<string, ll> dist;
    queue<string> q;

    dist[start_S] = 0;
    q.push(start_S);

    ll dy[] = {1, 0};
    ll dx[] = {0, 1};

    while (!q.empty()) {
        string cur = q.front();
        q.pop();

        if (cur == goal_S) {
            cout << dist[cur] << endl;
            return 0;
        }

        for (ll i = 0; i < N; ++i) {
            for (ll j = 0; j < 2 * N; ++j) {
                ll u = i * 2 * N + j;

                for (ll dir = 0; dir < 2; ++dir) {
                    ll ni = i + dy[dir];
                    ll nj = j + dx[dir];

                    if (ni < N && nj < 2 * N) {
                        ll v = ni * 2 * N + nj;
                        if (cur[u] != cur[v]) {
                            string nxt = cur;
                            swap(nxt[u], nxt[v]);
                            if (!dist.count(nxt)) {
                                dist[nxt] = dist[cur] + 1;
                                q.push(nxt);
                            }
                        }
                    }
                }
            }
        }
    }

    return 0;
}
0