#!/usr/bin/env python3 # Vladimír Sklenár import math from collections import deque def load_input(): R, S, K = map(int, input().split()) grid = [input() for _ in range(R)] return R, S, K, grid def bfs(R, S, K, mountain, start, end): directions = [(0, 1, 'V'), (0, -1, 'Z'), (-1, 0, 'S'), (1, 0, 'J')] dist = [[math.inf]*S for _ in range(R)] # Pole, které jsme objevili, určuje počet ponožek. # Na rekonstrukci cesty potřebujeme (předchozí řádek, předchozí sloupec, písmeno kroku). parent = [[None]*S for _ in range(R)] dist[start[0]][start[1]] = 0 dq = deque() # obousměrná fronta dq.append(start) while dq: x, y = dq.popleft() # Odebereme zepředu. if (x, y) == end: break # Když dorazíme do cíle, tak konec. for dx, dy, dir in directions: # Ze směrového vektoru vybíráme. nx, ny = x + dx, y + dy if 0 <= nx < R and 0 <= ny < S: new_cost = dist[x][y] + mountain[nx][ny] if new_cost < dist[nx][ny] and new_cost <= K: dist[nx][ny] = new_cost # Uložíme nový nejlepší počet ponožek. parent[nx][ny] = (x, y, dir) if not mountain[nx][ny]: # Pokud jsme šlápli na hlínu, přidáme na začátek. dq.appendleft((nx, ny)) else: # Pokud jsme šlápli na bláto, přidáme na konec. Díky tomu nejdřív projdeme suchou zem a až pak bláto. dq.append((nx, ny)) return parent def main(): R, S, K, grid = load_input() mountain = [] for i in range(R): mountain.append([]) for j in range(S): if grid[i][j] == 'U': start = (i, j) elif grid[i][j] == 'V': end = (i, j) mountain[-1].append(grid[i][j] == 'B') grid = [] # Odstraníme všechno z paměti, co už nepotřebujeme. parent = bfs(R, S, K, mountain, start, end) path = [] x, y = end # Vracíme se od konce do začátku. while (x, y) != start: previous = parent[x][y] assert previous is not None # Cesta neexistuje. px, py, dir = previous path.append(dir) x, y = px, py path.reverse() print(len(path)) for move in path: print(move) if __name__ == '__main__': main()