„MARVEL AT HIS MIGHT!”

Cerința

Zoli și D’Umbră s-au pierdut din nou prin labirintul cu n x n camere dispuse pe n linii și n coloane. De această dată, amândoi se află în camera (1, 1). A mai trecut de ultima dată și cateva lucruri s-au schimbat. Ei îl au acum la dispoziție pe Memobot, un roboțel controlat prin telecomandă care poate primi secvențe de comenzi. Când roboțelul primeste o secvență de comenzi, acesta va respecta fiecare comandă din secvență, apoi va aștepta o nouă comandă.

Din păcate pentru ei, Dr. Boom s-a plictisit să trimită Boom Bots (niște roboței care explodează singuri) să-i enerveze pe eroii din Azeroth. Așadar, acesta îi poziționează în câteva camere din labirint și care vor exploda când se vor afla în cameră cu înca cineva.

Acum Zoli și D’Umbră vor trebui să îl trimită pe Memobot pentru a curăța drumul până la ieșirea aflată în camera (n, n). Ajutați-i să iasă din labirint pe drumul cel mai scurt parcurs de Memobot! (Drumul cel mai scurt este, bineînțeles, cel ce conține un număr minim de secvențe de comenzi)

Date de intrare

Fișierul de intrare labirint2.in conține pe prima linie numerele n (dimensiunea labirintului), b (numărul de Boom Bots pe care Dr. Boom îi poziționează în labirint), s (numărul de secvențe de comenzi) și k (numărul de comenzi din fiecare secvență).

Pe următoarele b linii se află câte o pereche de numere naturale x și y reprezentând faptul că Dr. Boom a trimis un Boom Bot în camera aflată la coordonatele (x, y).

Pe următoarele s linii se află cate k litere din mulțimea {'U', 'D', 'L', 'R'} care reprezintă direcția spre care se va deplasa Memobot în secvență. (U – Sus, D – Jos, L – Stânga, R – Dreapta).

Date de ieșire

Fișierul de ieșire labirint2.out va conține pe prima linie numărul S, reprezentând numărul minim de secvențe de comenzi pe care Memobot trebuie să le primească.

Restricții și precizări

1 ≤ n ≤ 400
1 ≤ b ≤ n * n
1 ≤ k, s ≤ 10
Ordinea comenzilor din fiecare secvență nu poate fi schimbată!
Memobot poate trece de două ori prin aceeași cameră.
Pentru 30% din teste, k = 1, s = 4 și secvențele sunt diferite între ele. (Memobot va putea merge pe direcțiile simple: Dreapta, Stânga, Sus și Jos)
Dacă Memobot primește o secvență de comenzi care îl conduc spre o cameră inexistentă (pe linia/coloana 0 sau n + 1), atunci Memobot nu va executa secvența.
Dacă cel puțin 2 Boom Bots se află într-o cameră, aceștia vor exploda înainte ca Memobot să pornească.
Dacă nu există nici un drum prin care Memobot să ajungă în camera (n, n), atunci se va afișa mesajul ”Imposibil!”
Personajul este D’Umbră și nu Dumbră, și Dr. Boom este sigur de acest lucru.

Exemplu

labirint2.in

4 3 4 2
3 2
3 3
4 1
D R
D L
U R
D D

labirint2.out

Explicație

Comenzile sunt, în această ordine: (D, R), (U, R), (D, R), (D, D)

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Labirint2:

#include <fstream>
#include <queue>
using namespace std;

ifstream fin ("labirint2.in");
ofstream fout ("labirint2.out");

const int N = 405;

int dx[10][10], dy[10][10], n, b, s, k, a[N][N];
short d[N][N];
queue <pair <int, int> > Q;

int main() {
    fin >> n >> b >> s >> k;
    for (int x, y, i = 0; i < b; ++i) {
        fin >> x >> y;
        a[x-1][y-1]++;
    }
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            if (a[i][j] != 1)
                a[i][j] = 0;
    for (int i = 0; i < s; ++i)
        for (int j = 0; j < k; ++j) {
            string s;
            fin >> s;
            if (s == "L")
                dx[i][j] = 0, dy[i][j] = -1;
            if (s == "R")
                dx[i][j] = 0, dy[i][j] = 1;
            if (s == "U")
                dx[i][j] = -1, dy[i][j] = 0;
            if (s == "D")
                dx[i][j] = 1, dy[i][j] = 0;
        }
    Q.push(make_pair (0, 0));
    d[0][0] = 1;
    while (Q.size()) {
        int x = Q.front().first;
        int y = Q.front().second;
        Q.pop();
        int xx = x;
        int yy = y;
        for (int i = 0; i < s; ++i) {
            xx = x;
            yy = y;
            bool ok = 1;
            for (int j = 0; j < k; ++j) {
                xx += dx[i][j];
                yy += dy[i][j];
                if (xx < 0 || yy < 0 || xx >= n || yy >= n || a[xx][yy]) {
                    ok = 0;
                    break;
                }
            }
            if (ok && !d[xx][yy]) {
                d[xx][yy] = d[x][y] + 1;
                Q.push(make_pair (xx, yy));
            }
        }
    }
    /*for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j)
            fout << a[i][j] << " ";
        fout << "\n";
    }
    fout << "\n";*/
    /*for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j)
            fout << d[i][j] << " ";
        fout << "\n";
    }*/
    if (!d[n-1][n-1])
        fout << "Imposibil!";
    else
        fout << d[n-1][n-1] - 1;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1241 Labirint2

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1241 Labirint2 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1241 Labirint2