Submission #63072624

---

Source Code Expand

#include <bits/stdc++.h>
//#define int long long 
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define fr first
#define se second
#define endl '\n'
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
mt19937_64 rnd(time(0));

const int N = 2e5 + 10;

int n;
char c[110][110];
int dp[110][110];

void solve()
{
	cin >> n;
	queue<array<int,3>> q;
	for(int i = 1; i <= n; i ++){
		for(int j = 1; j <= n; j ++){
			cin >> c[i][j];
			if(i == j){
				dp[i][i] = 0;
				q.push({i, i, 0});
			}
			else if(c[i][j] != '-'){
				dp[i][j] = 1;
				q.push({i, j, 1});
			}
			else dp[i][j] = inf;
		}
	}

	while(q.size()){
		auto [x, y, len] = q.front();
		q.pop();
		// 枚举新的开头
		for(int i = 1; i <= n; i++){
			if(c[i][x] != '-'){
				// 枚举新的结尾
				for(int j = 1; j <= n; j ++){
					if(c[y][j] == c[i][x] && dp[i][j] > len + 2){
						dp[i][j] = len + 2;
						q.push({i, j, dp[i][j]});
					}
				}
			}
		}
	}

	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j ++){
			if(dp[i][j] == inf){
				cout << -1 << ' ';
			}
			else{
				cout << dp[i][j] << ' ';
			}
		}
		cout << endl;
	}

}


signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T=1; //cin>>T;
	while(T--) solve();
	return 0;
}

Submission Info

Judge Result