[백준] 12875 칙령

문제를 읽고 그림을 그려보면 플로이드 문제인게 보인다

각각 친구보다만 x-d~x+d 이기 때문에 max(두 정점사이거리)*d가 답이다

소스코드

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int d[55][55];
char a[55][55];
int n, k;
int main() {
    scanf(" %d %d", &n, &k);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            d[i][j] = 1e9;
        }
    }
    for (int i = 0; i < n; i++) scanf(" %s", &a[i]), d[i][i] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (a[i][j] == 'Y') d[i][j] = 1;
        }
    }
    
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            ans = max(ans, d[i][j]);
        }
    }
    if (ans == 1e9) puts("-1");
    else printf("%d\n", ans*k);
}