No.455 冬の大三角

yukicoderのAdventカレンダー問題、まだコレしか着手できてない…。

問題

No.455 冬の大三角 - yukicoder

ある2点が星になっている地図があるので、もう1点を星にして（どんな形でも良い）三角形を作る問題。

方針

ある1点について隣接する上下左右の4隅のどこかに星の候補場所を置き、三角形にならないパターンだけを探しました。2点は隣接しているので、その延長線上にもう1つの星が配置されていないかどうかを確認すれば大丈夫ですね。

ちなみにコーナーケースにかなり苦しめられました。7WAってひどくないですかね。。。
また、恐らく乱択とかして頑張ってもなんとかなるんじゃないかなと思います。。。

あまりきれいに書けなかった *1ので、他の人のプログラムを後で参考にしよう。。。

#135821 No.455 冬の大三角 - yukicoder

def solve():
    w, h = map(int, input().split())
    px, py, qx, qy = -1, -1, -1, -1
    for y in range(w):
        line = input()
        while "*" in line:
            idx = line.find("*")
            if px == -1:
                px, py = idx, y
            else:
                if len(line) == h:
                    qx, qy = idx, y
                else:
                    qx, qy = idx + px + 1, y
            line = line[idx+1:]
    tx, ty = -1, -1
    patternlist = [[px-1, px+1, qx-1, qx+1], [py-1, py+1, qy-1, qy+1]]
    for j in range(4):
        for k in range(4):
            x, y = patternlist[0][j], patternlist[1][k]
            if (0 <= x < h and 0 <= y < w) \
                and (not(x == px and y == py)) and (not(x == qx and y == qy)) \
                and not(px - x == py - y and qx - x == qy - y):
                tx, ty = x, y
                break
        if tx != -1:
            break

    points = [[px, qx, tx], [py, qy, ty]]
    ans = [list("-" * h) for _ in range(w)]
    for i in range(3):
        ans[points[1][i]][points[0][i]] = "*"
    print("\n".join(["".join(line) for line in ans]))

if __name__=="__main__":
    solve()

*1: 一直線かどうかを判定するところが非常に汚い