霧島京子からの挑戦状 7924pt https://paiza.jp/moshijo/share/moshijo_character_10/challenge_result/ad90853b

dungeon.py

import re
from queue import PriorityQueue

class Tile:
    def __init__(self, blocked=False, lb="", isKey=False, isTrap=False):
        self.blocked = blocked
        self.lb = lb
        self.isKey = isKey
        self.isTrap = isTrap
    
    def __str__(self):
        if self.blocked:
            return "#"
        if self.isKey:
            return self.lb
        if self.isTrap:
            return self.lb.upper()
        return "."
    
    def damage(self, keys):
        if self.isTrap and self.lb not in keys:
            return 100
        return 1

def parseTile(t):
  if t == ".":
    return Tile()
  if t == "#":
    return Tile(True)
  if re.match(r"[a-z]", t):
    return Tile(False, t, True, False)
  if re.match(r"[A-Z]", t):
    return Tile(False, t.lower(), False, True)
    
class TileMap:
    def __init__(self, tileMap=None):
        self.tileMap = tileMap
        self.keys = []
    
    def __str__(self):
        res = ""
        for row in self.tileMap:
            for t in row:
                res += str(t)
            res += "\n"
        return res
        
    def getTile(self, coor):
        x, y = coor
        return self.tileMap[y][x]
    
    def neighbours(self, coor):
        dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        res = []
        for d in dirs:
            n = (d[0] + coor[0], d[1] + coor[1])
            if n[0] >= 0 and n[0] < len(self.tileMap[0]) \
            and n[1] >= 0 and n[1] < len(self.tileMap) \
            and not self.getTile(n).blocked:
                res.append(n)
        return res
    
    def cost(self, coor):
        return self.getTile(coor).damage(self.keys)
    
    def getKey(self, coor):
        if self.getTile(coor).isKey:
            self.keys.append(self.getTile(coor).lb)
        
    def pathFinder(self, start, goal):
        # dijkstra as first pass
        frontier = PriorityQueue()
        frontier.put((0, start))
        cameFrom = {}
        cameFrom[start] = None
        costSoFar = {}
        costSoFar[start] = 0
        
        while not frontier.empty():
            current = frontier.get()[1]
            
            if current == goal:
                break
            
            for next in self.neighbours(current):
                self.getKey(current)
                newCost = costSoFar[current] + self.cost(next)
                if next not in costSoFar or newCost < costSoFar[next]:
                    costSoFar[next] = newCost
                    frontier.put((newCost, next))
                    cameFrom[next] = current

        current = goal
        path = [current]
        while current != start:
            current = cameFrom[current]
            path.append(current)
        path.append(start)
        path.reverse()
        
        return path
    
    def getPathStr(self, start, goal):
        path = self.pathFinder(start, goal)
        res = ""
        for p, n in zip(path[:-1], path[1:]):
            d = (n[0] - p[0], n[1] - p[1])
            if d == (0, 1):
                res += "D\n"
            elif d == (1, 0):
                res += "R\n"
            elif d == (0, -1):
                res += "U\n"
            elif d == (-1, 0):
                res += "L\n"
        return res
        

line = input()
h, w, n = tuple(map(int, line.strip().split(' ')))

tiless = []
for hi in range(h):
    line = input()
    tiles = list(map(parseTile, list(line)))
    tiless.append(tiles)
tmap = TileMap(tiless)

line = input()
start = tuple(map(lambda x: int(x) - 1, line.split(' ')))
line = input()
end = tuple(map(lambda x: int(x) - 1, line.split(' ')))

print(tmap.getPathStr(start, end))