Tekst zadatka

Malena Sia se izgubila u velikom, pravokutnom labirintu! Labirint se sastoji od polja koja mogu biti ili zid (#) ili slobodan put (.). Sia počinje na početnoj poziciji označeno s 'S' i želi doći do izlazne pozicije označene s 'E'.

Labirint je zadan dimenzijama N i M. Stvarna mreža (grid) koja predstavlja labirint ima dimenzije (2N+1) x (2M+1). Ćelije s obje neparne koordinate (npr. (1,1), (1,3), (3,1)) predstavljaju slobodna polja ili početak/kraj, dok ostale ćelije mogu biti zidovi (#) ili dijelovi puta (.) koji povezuju susjedna slobodna polja.

Sia kreće iz gornjeg lijevog slobodnog polja na koordinatama (1, 1). Njen cilj je doći do donjeg desnog slobodnog polja na koordinatama (2N - 1, 2M - 1).

Sia ne vidi cijeli labirint odjednom. Ona može pokušati napraviti pomak u jednom od četiri smjera: gore (U), dolje (D), lijevo (L) ili desno (R). Nakon svakog pokušaja pomaka, sustav za ocjenjivanje (grader) će joj javiti što se dogodilo.

Vaš zadatak je napisati program koji će upravljati Sijinim kretanjem i dovesti je do izlaza.

Interakcija

Na početku interakcije, vaš program treba pročitati dva cijela broja, N i M, koji predstavljaju dimenzije labirinta.

Nakon toga, vaš program treba slati naredbe za pomak, jednu po jednu. Svaka naredba mora biti jedan od znakova: 'U', 'D', 'L', 'R', nakon čega slijedi znak za novi red. Važno: Nakon ispisa svake naredbe, morate isprazniti izlazni spremnik (npr. sys.stdout.flush() u Pythonu, fflush(stdout) u C++, System.out.flush() u Javi).

Nakon svake poslane naredbe, vaš program treba pročitati povratnu informaciju od gradera. Povratna informacija će biti jedna od sljedećih poruka (završena znakom za novi red):

1. MOVED r c : Pomak je bio uspješan. Sia se sada nalazi na koordinatama (r, c).
2. BLOCKED r c: Pomak nije bio moguć jer se u tom smjeru nalazi zid. Sia je ostala na prethodnoj poziciji (r, c).
3. OK r c : Pomak je bio uspješan i Sia je stigla na izlaznu poziciju (r, c). Nakon ove poruke, vaš program treba završiti s izvođenjem.

Vaš program treba nastaviti slati naredbe i čitati povratne informacije sve dok ne primi poruku OK.

Ulazni format

Prvi i jedini red standardnog ulaza sadrži dva cijela broja N i M, odvojena razmakom - dimenzije labirinta.

Izlazni format

Vaš program treba ispisivati naredbe za pomak ('U', 'D', 'L', 'R') na standardni izlaz, svaku u svom redu. Ne zaboravite isprazniti izlazni spremnik nakon svakog ispisa.

Ograničenja

• 1 <= N, M <= 15
• Početna pozicija je uvijek (1, 1).
• Ciljna pozicija je uvijek (2N - 1, 2M - 1).
• Jamči se da labirint uvijek ima rješenje (postoji barem jedan put od početka do kraja).

Podzadatci

Primjer interakcije

Pretpostavimo da je N=2, M=2 ispis evaluatora:

--- Starting Grader Interaction ---
[GRADER] interact() started.
[GRADER] Read n=2, m=2 from case data.
[GRADER] Maze generated.
#####
#S#.#
#.#.#
#..E#
#####
[GRADER] Maze determined to be SOLVABLE.
[GRADER] Writing initial data: '2 2'
INTERACTOR (write): >>> 2 2
[GRADER] Initial data written.
[GRADER] Waiting for move 1 (current pos: [1, 1])...
INTERACTOR (readln): <<< b'D\n'
[GRADER] Read bytes: b'D\n', Decoded command: 'D'
[GRADER] Processing move 'D': Current pos [1, 1], attempting 2,1
[GRADER] Move successful. New pos 2,1. Sending MOVED.
INTERACTOR (write): >>> MOVED 2 1
[GRADER] Waiting for move 2 (current pos: [2, 1])...
INTERACTOR (readln): <<< b'D\n'
[GRADER] Read bytes: b'D\n', Decoded command: 'D'
[GRADER] Processing move 'D': Current pos [2, 1], attempting 3,1
[GRADER] Move successful. New pos 3,1. Sending MOVED.
INTERACTOR (write): >>> MOVED 3 1
[GRADER] Waiting for move 3 (current pos: [3, 1])...
INTERACTOR (readln): <<< b'D\n'
[GRADER] Read bytes: b'D\n', Decoded command: 'D'
[GRADER] Processing move 'D': Current pos [3, 1], attempting 4,1
[GRADER] Move blocked. Pos remains [3, 1]. Sending BLOCKED.
INTERACTOR (write): >>> BLOCKED 3 1
[GRADER] Waiting for move 4 (current pos: [3, 1])...
INTERACTOR (readln): <<< b'R\n'
[GRADER] Read bytes: b'R\n', Decoded command: 'R'
[GRADER] Processing move 'R': Current pos [3, 1], attempting 3,2
[GRADER] Move successful. New pos 3,2. Sending MOVED.
INTERACTOR (write): >>> MOVED 3 2
[GRADER] Waiting for move 5 (current pos: [3, 2])...
INTERACTOR (readln): <<< b'D\n'
[GRADER] Read bytes: b'D\n', Decoded command: 'D'
[GRADER] Processing move 'D': Current pos [3, 2], attempting 4,2
[GRADER] Move blocked. Pos remains [3, 2]. Sending BLOCKED.
INTERACTOR (write): >>> BLOCKED 3 2
[GRADER] Waiting for move 6 (current pos: [3, 2])...
INTERACTOR (readln): <<< b'R\n'
[GRADER] Read bytes: b'R\n', Decoded command: 'R'
[GRADER] Processing move 'R': Current pos [3, 2], attempting 3,3
[GRADER] Move successful. Reached END at 3,3. Sending OK.
INTERACTOR (write): >>> OK 3 3
[GRADER] OK sent. Interaction successful.

Python template

import sys


class MazeSolver:
    """Klasa za rješavanje labirinta."""

    def __init__(self):
        """Inicijalizira rješavač, čita dimenzije labirinta."""
        self.n = 0
        self.m = 0
        self.start_pos = (1, 1)
        self.end_pos = None
        self.move_map = {"U": (-1, 0), "D": (1, 0), "L": (0, -1), "R": (0, 1)}
        self.opposite_move = {"D": "U", "U": "D", "R": "L", "L": "R"}
        self.visited = set()
        self._read_initial_dimensions()

    def _read_initial_dimensions(self):
        """Čita dimenzije labirinta iz stdin-a."""
        byte_line = sys.stdin.buffer.readline()

        line = byte_line.decode("utf-8").strip()

        self.n, self.m = map(int, line.split())
        self.end_pos = (2 * self.n - 1, 2 * self.m - 1)

    def _read_feedback(self) -> str | None:
        """Čita liniju povratne informacije iz stdout-a, vraća dekodirani string ili None na EOF."""
        feedback_bytes = sys.stdin.buffer.readline()
        if not feedback_bytes:
            return None
        feedback = feedback_bytes.decode("utf-8").strip()
        return feedback

    def _send_move(self, move_char: str):
        """Dekodira i šalje naredbu za pomak (stdout)."""
        move_bytes = move_char.encode("utf-8") + b"\n"
        sys.stdout.buffer.write(move_bytes)
        sys.stdout.buffer.flush()

    def solve(self):
        """Rješava labirint TODO: Implementirati rješenje."""

        return False


if __name__ == "__main__":
    solver = MazeSolver()
    solved = solver.solve()

C++ template

#include <iostream>
#include <map>
#include <set>
#include <string>
#include <utility>
#include <vector>

using namespace std;

class MazeSolver {
private:
  int n = 0;
  int m = 0;
  pair<int, int> start_pos = {1, 1};
  pair<int, int> end_pos;
  map<char, pair<int, int>> move_map;
  map<char, char> opposite_move;
  set<pair<int, int>> visited;
  vector<char> preferred_moves = {'D', 'R', 'U', 'L'};

  void read_initial_dimensions() {
    cin >> n >> m;
    end_pos = {2 * n - 1, 2 * m - 1};
  }

  string read_feedback() {
    string feedback_line;
    if (getline(cin >> ws, feedback_line)) {
      return feedback_line;
    }
    return "";
  }

  void send_move(char move_char) { cout << move_char << endl; }

  pair<int, int> parse_coords(const string &feedback) {
    size_t first_space = feedback.find(' ');
    size_t second_space = feedback.find(' ', first_space + 1);
    if (first_space == string::npos || second_space == string::npos) {
      throw runtime_error("Could not parse coordinates from feedback: " +
                          feedback);
    }
    int r =
        stoi(feedback.substr(first_space + 1, second_space - first_space - 1));
    int c = stoi(feedback.substr(second_space + 1));
    return {r, c};
  }

public:
  MazeSolver() {
    move_map['U'] = {-1, 0};
    move_map['D'] = {1, 0};
    move_map['L'] = {0, -1};
    move_map['R'] = {0, 1};

    opposite_move['D'] = 'U';
    opposite_move['U'] = 'D';
    opposite_move['R'] = 'L';
    opposite_move['L'] = 'R';

    read_initial_dimensions();
  }

  bool solve() { return false; }
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  MazeSolver solver;
  solver.solve();

  return 0;
}