Cerința

Cătălin s-a pierdut iarăși într-o matrice de N linii și M coloane în care unele celule sunt blocate. Cătălin nu găsește ieșirea așa că s-a decis să caute o comoară. El are o harta pe care a desenat-o când era mic și decide să o urmeze. Pe harta este scris un șir format din caracterele U, R, D, L. În fiecare secundă Cătălin se va deplasa în una dintre cele 4 celule adiacente. Presupunând că la secunda S Cătălin se află în celula i, j el se va mișcă în funcție de al S-lea caracter de pe harta în felul următor: pentru U el va păși în celula i - 1, j; pentru R el va păși în celula i, j + 1; pentru D el va păși în celula i + 1, j, iar pentru L, el va păși în celula i, j - 1.

Dacă celula în care trebuie să pășească este în afara matricei sau este blocată, atunci Cătălin va sta pe loc în acea secunda. În ce celulă ajunge Cătălin?

Date de intrare

Pe prima linie a fișierului de intrare​ labirint4.in ​se vor afla 3 numere naturale N, M și K. Pe următoarele K linii se vor afla cate 2 numere reprezentând linia și coloana unei celule blocate. Pe următoarea linie se vor afla 2 numere naturale reprezentând linia, respectiv coloana de pe care începe Cătălin să se miște. Pe ultima linie se va afla numărul de caractere din șirul de pe hartă urmat de acele caractere.

Date de ieșire

În fișierul de ieșire​ labirint4.out​ se vor afla două numere reprezentând linia și coloana pe care ajunge Cătălin.

Restricții și precizări

• 1 ≤ lungimea șirului de pe hartă ≤ 10000
• Pentru 20 de puncte 1 ≤ N, M ≤ 10000 și K = 0
• Pentru alte 60 de puncte: 1 ≤ N, M ≤ 500 și 1 ≤ K ≤ N * M
• Pentru restul de puncte: 1 ≤ N, M ≤ 10000 și 1 ≤ K ≤ 1000

Exemplu

labirint4.in

4 5 7
1 3
1 5 
2 1 
2 4 
2 5 
3 1
3 2
2 2
11
ULRDDRDRDLU 

labirint4.out

3 3

Explicație

Traseul lui Catalin este:
(2, 2) → (1, 2) → (1, 1) → (1, 2) → (2, 2) → (2, 3) → (3, 3) → (3, 4) → (4, 4) → (4, 3) → (3, 3)

#include <bits/stdc++.h>

using namespace std;
ifstream cin("labirint4.in");
ofstream cout("labirint4.out");

struct pozitie
{
    int i , j;
};

pozitie o[250000] , C;
int n , m , k , p;
char ch;

int comparare(pozitie a , pozitie b)
{
    return a.i<b.i || a.i == b.i && a.j < b.j;
}

int libera(int x , int y)
{
    int st = 1 , dr = k;
    while(st <= dr)
    {
        int mij = (st + dr) / 2;
        if(o[mij].i == x && o[mij].j == y) return 0;
        else
        {
            pozitie c;
            c.i = x;
            c.j = y;
            if(comparare(o[mij] , c)) st = mij+1;
            else dr = mij - 1;
        }
    }
    return 1;
}
int main()
{
    cin >> n >> m >> k;
    for(int i = 1 ; i <= k ; i++)
        cin >> o[i].i >> o[i].j;
    cin >> C.i >> C.j;
    sort(o+1 , o+k+1 , comparare);
    cin >> p;
    for(int i = 1; i <= p ; i++)
    {
        cin >> ch;
        if(ch == 'U' )
        {
            if(C.i-1 >= 1 && libera(C.i-1 , C.j))
                C.i--;
        }
        else
            if(ch == 'R' )
            {
                if(C.j+1 <=m && libera(C.i , C.j+1))
                    C.j++;
            }
        else
            if(ch == 'D')
            {
                if(C.i+1 <= n  && libera(C.i+1 , C.j))
                C.i++;
            }
        else if(ch == 'L')
        {
            if(C.j-1 >= 1 && libera(C.i , C.j-1))
                C.j--;
        }
    }
    cout << C.i << ' ' << C.j;
}