# PBinfo #4641 – drar – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

Domnișoara R este o tânără foarte pasionată de medicină. Aceasta, pregătindu-se constant pentru admiterea la UMF, constată că are un obstacol – Stresu’. Domnișoara R are o casă cu N x M camere, aranjate pe N linii (numerotate de la 1 la N) și M coloane (numerotate de la 1 la M), dintre care B camere sunt inaccesibile (nu este permis accesul în acestea). Vom nota cu [i, j] (1 ≤ i ≤ N, 1 ≤ j ≤ M) camera situată pe linia i și coloana j. Pentru că Universul este neprietenos, vrea să îi pună bețe în roate d-rei. R și astfel îl trimite pe Stresu’ în casa acesteia în camera [X,Y], care este o cameră accesibilă. Stresu’ se poate deplasa în orice cameră adiacentă camerei în care se află (situată pe aceeași linie pe o coloană alăturată sau pe aceeași coloană pe o linie alăturată) sau își poate folosi unul dintre așii din mânecă. Stresu’ dispune de Q ași. Când utilizează asul cu numărul i (1 ≤ i ≤ Q) Stresu’ se poate deplasa din camera [L1i, C1i] în camera [L2i, C2i]. Orice deplasare (utilizând un as sau într-o cameră adiacentă) necesită o secundă și deplasarea nu poate fi efectuată dacă presupune revenirea în ultima cameră care a fost vizitată. Se garantează că dacă există un as în mânecă de la camera [L1,C1] la camera [L2,C2], nu va exista un alt as de la camera [L2,C2] la camera [L1,C1]. 

Dra. R se află inițial în camera [1, 1]. Când aceasta constată că Stresu’ a intrat în casă, se panichează și urmează un traseu ilustrat printr-un șir de caractere care descrie direcțiile de deplasare:


L – din camera [i, j] se va deplasa în camera [i, j − 1]
R – din camera [i, j] se va deplasa în camera [i, j + 1]
U – din camera [i, j] se va deplasa în camera [i − 1, j]
D – din camera [i, j] se va deplasa în camera [i + 1, j]

Se garantează că d-ra R nu va trece prin camere inaccesibile. Stresu’ și d-ra R nu pot staționa în camere, fiecare dintre ei trebuie să efectueze o deplasare la fiecare secundă.

Cerința
Știind că scopul lui Stresu’ este să o prindă pe d-ra R, scrieți un program care să determine timpul minim în care Stresu’ poate ajunge în aceeași cameră cu d-ra R.

Date de intrare
Fișierul de intrare drar.in conține pe prima linie numerele N M Q X Y B, reprezentând dimensiunile casei d-rei R, numărul de ași din mâneca lui Stresu’, coordonatele camerei pe unde intră Stresu’, respectiv numărul de camere inaccesibile. Următoarele B linii conțin camerele inaccesibile, câte o cameră pe o linie. Pe următoarele Q linii sunt descriși așii, câte un as pe o linie, sub forma celor 4 numere L1i C1i L2i C2i, (1 ≤ i ≤ Q) cu semnificația din enunț. Pe ultima linie din fișier se va afla șirul de caractere care descrie modul în care se deplasează d-ra R. Numerele scrise pe aceeași linie sunt separate prin câte un spațiu.

Date de ieșire
Fișierul de ieșire drar.out va conține o singură linie pe care va fi scris timpul minim în care Stresu’ poate ajunge în aceeași cameră cu d-ra R sau valoarea −1 dacă acest lucru nu este posibil.

Restricții și precizări

1 ≤ N, M ≤ 200
1 ≤ X ≤ N, 1 ≤ Y ≤ M
0 ≤ Q ≤ 1000
0 ≤ B ≤ N x M
1 ≤ L1i, L2i ≤ N, 1 ≤ C1i, C2i ≤ M
1 ≤ lungimea traseului ≤ 200
Pentru 10 puncte, X = Y = 1
Pentru 30 de puncte, 1 ≤ N, M ≤ 6, 0 ≤ Q ≤ 3
Pentru 30 de puncte, 7 ≤ N, M ≤ 50
Pentru 30 de puncte, nu există restricții suplimentare.

Exemplu:
drar.in

6 6 4 5 2 5
2 1
4 4
2 4
3 2
2 6
6 4 2 2
3 4 2 3
5 1 2 5
3 5 3 3
RRRRDD
drar.out

6

## Cod sursă C++

```cpp
#include <fstream>
#define f first
#define s second
const int NMAX=505;
const int QMAX=1005;
using namespace std;
ifstream fin("drar.in");
ofstream fout("drar.out");
bool dp[3][6][NMAX][NMAX];
///dp[k][s][i][j]=true, daca poate ajunge stresu
///in [i, j] prin k pasi <=> k timp (k%2-pt memorie)
///stiind ca ultima data a fost in camera [i+dl[s], j+dc[s]]
///s=4 reprezinta ca s-a ajuns printr-un as
///nu ne intereseaza sa stocam ce as datorita restrictiei
int dl[]= {0, 0, -1, 1, 5};
int dc[]= {-1, 1, 0, 0, 7};
int n, m, q, x, y, nb;
pair<int, int> v[QMAX], vv[QMAX], timp[NMAX];
char t[NMAX];
bool bloc[NMAX][NMAX];
bool inside(int, int);
bool ad(int, int, int, int);
int main()
{
    int prec=0, crt=1;
    int l=1, c=1, lg=0;
    int i, j, k, d, s, a, b;
    fin>>n>>m>>q>>x>>y>>nb;
    for(i=1; i<=nb; i++)
    {
        fin>>a>>b;
        bloc[a][b]=true;
    }
    dp[prec][4][x][y]=true;
    for(i=1; i<=q; i++)
    {
        fin>>v[i].f>>v[i].s;
        fin>>vv[i].f>>vv[i].s;
    }
    fin>>t;
    if(x==1 && y==1) ///timpul minim e 0
    {
        fout<<0<<'\n';
        return 0;
    }
    timp[0]= {1, 1};
    ///nu e necesar sa initializez timp[i][j] cu 1e9
    ///pt ca verific timpul 0 separat
    for(lg=0; t[lg]; lg++)
    {
        if(t[lg]=='R') c++;
        if(t[lg]=='L') c--;
        if(t[lg]=='U') l--;
        if(t[lg]=='D') l++;
        timp[lg+1]= {l, c};
    }
    for(k=1; k<=lg; k++)
    {
        for(i=1; i<=n; i++)
        {
            for(j=1; j<=m; j++)
            {
                for(d=0; d<5; d++)
                {
                    dp[crt][d][i][j]=false;
                }
            }
        }
        ///adiacente
        for(i=1; i<=n; i++)
        {
            for(j=1; j<=m; j++)
            {
                if(!bloc[i][j])
                {
                    for(d=0; d<4; d++)
                    {
                        if(inside(i+dl[d], j+dc[d]))
                        {
                            for(s=0; s<5; s++)
                            {
                                ///conditia cu ultima camera
                                ///a=[i, j]
                                ///aa=[i+dl[d], j+dc[d]]
                                ///aaa=[i+dl[d]+dl[s], j+dc[d]+dc[s]]
                                ///aaa -> aa -> a
                                ///dp[crt][d][i][j] -> imi zice ca am venit in [i, j] din [i+dl[d], j+dc[d]]
                                ///dp[prec][s][i+dl[d]][j+dc[d]] -> am venit in [i+dl[d], j+dc[d]] din [i+dl[d]+dl[s], j+dc[d]+dc[s]]
                                ///aaa!=a -> dl[d]+dl[s]!=0 || dc[d]+dc[s]!=0
                                if(dl[d]+dl[s]!=0 || dc[d]+dc[s]!=0)
                                    dp[crt][d][i][j]|=dp[prec][s][i+dl[d]][j+dc[d]];
                            }
                        }
                        if(timp[k].f==i && timp[k].s==j && dp[crt][d][i][j])
                        {
                            ///am gasit solutie in timpul minim k
                            fout<<k<<'\n';
                            return 0;
                        }
                    }
                }
            }
        }
        for(i=1; i<=q; i++) ///asi
        {
            ///daca sunt adiacente dau skip pt ca am verificat inainte
            if(!bloc[vv[i].f][vv[i].s] && !ad(vv[i].f, vv[i].s, v[i].f, v[i].s))
            {
                for(d=0; d<5; d++)
                    dp[crt][4][vv[i].f][vv[i].s]|=dp[prec][d][v[i].f][v[i].s];
                if(timp[k]==vv[i] && dp[crt][4][vv[i].f][vv[i].s])
                {
                    ///am gasit solutie in timpul minim k
                    fout<<k<<'\n';
                    return 0;
                }
            }
        }
        crt=1-crt;
        prec=1-prec;
    }
    fout<<-1<<'\n';
    return 0;
}
bool inside(int lin, int col)
{
    return (lin>=1 && lin<=n && col>=1 && col<=m);
}
bool ad(int l1, int c1, int l2, int c2)
{
    int i;
    for(i=0; i<4; i++)
    {
        if(l1+dl[i]==l2 && c1+dc[i]==c2)
            return true;
    }
    return false;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4641)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4641/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4641/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)