書道 [yukicoder No.707]

https://yukicoder.me/problems/no/707

解法

https://yukicoder.me/submissions/270304
　
まず、これは個人的なおすすめなのだが、実装が大変そうな問題では、添字を0-indexではなく1-indexで書くと良い。
こうすることで、デバッグが個人的にしやすい。
　
愚直に全探索シミュレーションしていこう。
立てる所はO(H+W)で、マスとの距離計算もO(HW)なので、全探索シミュレーションで間に合う。
　
自分の実装では「立つマス(sx, sy)を全探索→黒マスとの距離を計算→最小値をとる」である。
立つマスの全探索は、立てないところをcontinueで飛ばすことにしてある。

int H, W;
string P[55];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W;
    rep(y, 1, H + 1) cin >> P[y];

    double ans = 1e9;
    rep(sx, 0, W + 2) rep(sy, 0, H + 2) {
        // 紙内部
        if (1 <= sx and sx <= W and 1 <= sy and sy <= H) continue;
        // 四隅
        if ((sx == 0 or sx == W + 1) and (sy == 0 or sy == H + 1)) continue;

        double sm = 0;
        rep(y, 1, H + 1) rep(x, 1, W + 1) if (P[y][x-1] == '1') {
            double dx = sx - x;
            double dy = sy - y;
            sm += sqrt(dx * dx + dy * dy);
        }
        chmin(ans, sm);
    }

    printf("%.10f\n", ans);
}