提出 #63055980

---

ソースコード 拡げる

#ifndef ATCODER // AtCoder 環境でない場合はデバッグモードを有効にする. コンパイルにすごく時間がかかる！
#define _GLIBCXX_DEBUG // out of rangeを検出してくれる。#include<bits/stdc++.h>の前に記述する必要あり
#endif
#include<bits/stdc++.h>
using namespace std;
struct IOSetup {
    IOSetup() {
        // 実行が高速化するコード
        cin.tie(nullptr);
        ios_base::sync_with_stdio(false);
        // 小数点以下10桁まで(四捨五入)
        cout << fixed << setprecision(10);
    }
} iosetup;
#define rep(i, n) for (int i = 0; i < n; i++)
#define rep2(i, a, b) for (int i = a; i < b; i++)
#define rrep(i, b, a) for (int i = b; i > a; i--)
#define rep3(i, a, b, d) for (int i = a; i < b; i+=d)
#define rrep3(i, b, a, d) for (int i = b; i > a; i-=d)
#define between(x, a, b) (((a) <= (x)) && ((x) < (b)))

// Template function to print various container types
template<typename Container>
void print(const Container& a) {
    cout << "{";
    bool first = true;
    for (const auto& i : a) {
        if (!first) {
            cout << ",";
        }
        cout << i;
        first = false;
    }
    cout << "}" << endl;
}


// Template function to print 2D vector
template<typename T>
void printvec2d(const vector<vector<T>>& a) {
    size_t rows = a.size();
    for (size_t i = 0; i < rows; ++i) {
        print(a[i]);
    }
}

// Template function to print 3D vector
template<typename T>
void printvec3d(const vector<vector<vector<T>>>& a) {
    size_t depth = a.size();
    for (size_t i = 0; i < depth; ++i) {
        printvec2d(a[i]);
        cout << endl;
    }
}

int main() {
    int n;
    cin >> n;
    vector<vector<int>> ans(n, vector<int>(n));
    vector<string> C(n);
    rep(i, n) cin >> C[i];
    deque<tuple<int, int, int>> dq;
    vector<vector<int>> dist(n, vector<int>(n, -1));
    rep(i, n) {
        dist[i][i] = 0;
        dq.push_back({i, i, 0});
    }

    vector<vector<vector<int>>> g0(n, vector<vector<int>>(26));
    vector<vector<vector<int>>> g1(n, vector<vector<int>>(26));
    rep(i, n) {
        rep(j, n) {
            char x = C[i][j];
            if (x == '-') continue;
            g0[i][x - 'a'].push_back(j);
            g1[j][x - 'a'].push_back(i);
            if (dist[i][j] != 0) dist[i][j] = 1;
            dq.push_back({i, j, 1});
        }
    }

    while (!dq.empty()) {
        auto [s, t, d] = dq.front();
        dq.pop_front();
        rep(i, 26) {
            for (auto& s1 : g1[s][i]) {
                for (auto& t1 : g0[t][i]) {
                    if (dist[s1][t1] != -1) continue;
                    dist[s1][t1] = d + 2;
                    dq.push_back({s1, t1, d + 2});
                }
            }
        }
    }

    rep(i, n) {
        rep(j, n) {
            cout << dist[i][j] << " ";
        }
        cout << endl;
    }
}

提出情報

ジャッジ結果