ATC 001 A 深さ優先探索とARC 031 B 埋め立て

競技プログラミング

qiita.com

qiitaの初級編の問題。

ATC 001 A 深さ優先探索

深さ優先は、そのまんま

import sys

sys.setrecursionlimit(10000000)

f = []
h, w = 0, 0
def rec(y, x):
    if f[y][x] == 'g':
        return True
    f[y][x] = '#'
    ans = False
    for dy, dx in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        if 0 <= y+dy < h and 0 <= x+dx < w and f[y+dy][x+dx] != '#':
            ans |= rec(y+dy, x+dx)
    return ans


def main():
    global f, h, w
    h, w = [int(i) for i in input().split()]
    start = []
    for i in range(h):
        s = input()
        for j in range(w):
            if s[j] == 's':
                start = [i, j]
        f.append(list(s))
    print('Yes' if rec(*start) else 'No')


if __name__ == '__main__':
    main()

setrecursionlimitの値は適当です。1000ぐらいにしたらREで落ちたので。

ARC 031 B 埋め立て

問題は、10*10の 'o' or 'x' でできたマスのうち、'x' を 1 マスだけ 'o' に変えて、全ての 'o' の島をつなぐことができるか問う問題。

自分は、'x' のうち、上下左右が 'o' が、2 つ以上あるかどうかで、'o' に変える必要があるかどうかを検索した。全ての 'x' を試してもいい気がするが。あと、10 * 10 なので、戻す操作をせず、コピーして使うことにした。以下、ACコード

import sys

sys.setrecursionlimit(1000)


def rec(y, x, f):
    f[y][x] = 'x'
    for dy, dx in [[1, 0], [-1, 0], [0, -1], [0, 1]]:
        if 0 <= y+dy < 10 and 0 <= x+dx < 10 and f[y+dy][x+dx] == 'o':
            rec(y+dy, x+dx, f)


def main():
    field = [list(input()) for i in range(10)]
    choice = []
    for y in range(10):
        for x in range(10):
            count = 0
            for dy, dx in [[1, 0], [-1, 0], [0, -1], [0, 1]]:
                if 0 <= y+dy < 10 and 0 <= x+dx < 10 and field[y+dy][x+dx] == 'o':
                    count += 1
            if count >= 2:
                choice.append([y, x])
    ans = False
    for y, x in choice:
        f2 = [line.copy() for line in field]
        rec(y, x, f2)
        tmp = True
        bs = False
        for line in f2:
            for c in line:
                if c == 'o':
                    tmp = False
                    # break switch
                    bs = True
                    break
            if bs:
                break
        ans |= tmp
        if ans:
            break
    print('YES' if ans else 'NO')


if __name__ == '__main__':
    main()

今日はあんまし考えることがなかったな。 この調子で頑張るぞい。