AGC 043 A - Range Flip Find Route【Python】

問題はこちら。

問題の条件は右か下にしか動けないという制限があるのだが、最初それを見落としていた。

そういうわけで想定解法はdpらしいが(01)BFSっぽく実装している。このコード右か下にしか動けないという制約がない場合でもdx, dy をちょこっといじれば対応できるようになっている。

道にいる間は道を優先的に探索して、壁にいる間は壁を優先的に探索する。そして道から壁に移動するときだけコストを１払う。

import sys
from collections import deque
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
   INF = float('inf')
   dx = [1, 0]
   dy = [0, 1]
   
   H, W = map(int, readline().split())
   board = [readline().strip() for _ in range(H)]
   
   cost = [[INF]*W for _ in range(H)]
   q = deque([(0, 0)])
   cost[0][0] = 0
   while q:
       x, y = q.popleft()
       for i in range(2):
           nx, ny = x + dx[i], y + dy[i]
           if nx < 0 or W <= nx or ny < 0 or H <= ny:
               continue
           if cost[ny][nx] < INF:
               continue
           if board[y][x] == '.':
               if board[ny][nx] == '.':
                   cost[ny][nx] = cost[y][x]
                   q.appendleft((nx, ny))
               else:
                   cost[ny][nx] = cost[y][x] + 1
                   q.append((nx, ny))
           else:
               if board[ny][nx] == '.':
                   cost[ny][nx] = cost[y][x]
                   q.append((nx, ny))
               else:
                   cost[ny][nx] = cost[y][x]
                   q.appendleft((nx, ny))
                   
   ans = cost[-1][-1]
   if board[0][0] == '#':
       ans += 1
   print(ans)
   
if __name__ == "__main__":
  main()