ABC161-D_LunlunNumberをpythonで解いた（BFS）

DFS / BFSについて

• DFS: 到達可能かを探る。全探索。
• BFS: 最短経路を探る。見つかったら打ち切ったり。
• ※seenという名前だが、todoに入れたらseenに入る
• DFSも、全部BFSでいいのでは？（BFSで打ち切らなければ同じ？）

DFS

• 例題

  • A - 深さ優先探索

• 解法

from collections import deque 

H,W = map(int,input().split())
c = [input() for i in range(H)]

# スタート、ゴール地点探索
for i,h in enumerate(c):
    #print(i,h)
    for j,w in enumerate(h):
        #print(j,w)
        if w == 's':
            s_h = i
            s_w = j
        if w == 'g':
            g_h = i
            g_w = j

# ”候補スタック”作成　（スタート地点を入れておく）
todo = deque([[s_h,s_w]])
# ”済みリスト”作成　（未探索(=0)、探索済み(=1)）
seen = [[0]*W for i in range(H)]
seen[s_h][s_w] = 1

# 探索開始
# ”候補スタック”が空っぽになるまで
while len(todo) > 0:
    #todoから探索地点を1つ取り出す(pop)
    h,w = todo.pop()
    #次に行ける地点をtodoにpushする作業
    for i,j in ([1,0],[-1,0],[0,1],[0,-1]):
        next_h = h+i
        next_w = w+j
        if next_h < 0 or next_h >=H or next_w < 0 or next_w >= W:
            continue
        #次に行ける地点が”済みリスト”にない場合は
        #”済みリスト”入りして、”候補スタック”にpush
        elif c[next_h][next_w] != '#' and seen[next_h][next_w] == 0:
            seen[next_h][next_w] = 1
            todo.append([next_h,next_w])

# ”済みリスト”にゴール地点が含まれてるか判定
if seen[g_h][g_w] == 1:
    print('Yes')
else:
    print('No')

# 探索途中で'g'が見つかった時点でprint('Yes')でもいい

BFS

• 例題

  • ABC007_C

• 解法

R,C=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
maze=[list(input()) for i in range(R)]
sy-=1
sx-=1
gy-=1
gx-=1

from collections import deque

todo = deque([[sy,sx]])
seen = [[0]*C for i in range(R)]
ans = 0

while len(todo) > 0:
    y,x = todo.popleft()
    if y == gy and x == gx:
        break
    for i,j in ([1,0],[-1,0],[0,1],[0,-1]):
        ny = y+i
        nx = x+j
        if nx >= 0 and ny >= 0 and maze[ny][nx] != '#' and seen[ny][nx] == 0:
            todo.append([ny,nx])
            seen[ny][nx] = seen[y][x] + 1
print(seen[gy][gx])

ABC161-D_Lunlun Number

• 問題

  • ABC161-D_Lunlun Number

• 解法

k=int(input())

from collections import deque
todo = deque([i for i in range(1, 10)])
count = 0

while len(todo) > 0:
    value = todo.popleft()
    value_digit1 = value % 10
    count += 1
    if count == k:
        print(value)
        break
    if value_digit1==0:
        todo.append(10*value)
        todo.append(10*value+1)
    elif value_digit1==9:
        todo.append(10*value+8)
        todo.append(10*value+9)
    else:
        todo.append(10*value+value_digit1-1)
        todo.append(10*value+value_digit1)
        todo.append(10*value+value_digit1+1)