Renumitul nostru brutar a avut azi noapte un vis tare ciudat: acesta trăia într-un univers paralel în care nu omul îl mănâncă pe blat ci blatul îl mănâncă pe om… (eh, poate nu chiar atât de paralel). Astfel, brutarul nostru a fost atacat de blatul pe care tocmai îl pregătise (pentru prăjituri, evident) și a încercat să scape. Acesta a ieșit din brutărie și a ajuns în fața unui câmp de formă dreptunghiulară, cu dimensiunile cunoscute, ce poate fi împărțit în celule elementare cu latura de o unitate (exact ca o matrice!). Acesta poate intra pe câmp prin orice celulă a primei linii și trebuie să ajungă în orice celulă a ultimei linii (blatul se va întări până va ajunge acolo). Unele celule îi sunt inaccesibile din cauza diverselor obstacole (pietre, pomi, gropi,etc.)

Brutarul nostru se poate deplasa în 6 moduri:

• Din căsuța curentă în cele adiacente ( Nord, Vest, Sud, Est )
• Două mișcări speciale ce pot varia.

Mutările speciale vor fi citite din fișier și o mutare se va codifica astfel: xA yB, unde x și y sunt numere naturale nenule iar A și B sunt două caractere ce codifică direcția (A poate fi 'N' sau 'S' de la Nord respectiv Sud iar B poate fi ‘E’ sau ‘V’ de la Est respectiv Vest)

Ex. 5N 2V codifică mutarea 5 poziții spre Nord și 2 poziții spre Vest. (din poziția (x,y) ajunge în poziția (x-5, y-2))

O mutare specială se poate face dacă celula destinație nu este ocupată de un obstacol și dacă nu implică ieșirea brutarului din matrice.

Cerința

Brutarul vă roagă să îi specificați un traseu cu număr minim de celule parcurse, ce pornește de pe prima linie și se termină pe ultima linie, pentru a nu fi blătuit (mâncat de blat).

Date de intrare

Pe prima linie a fișierului brutar.in se vor afla două numere naturale separate prin spațiu: N și M reprezentând numărul de linii și numărul de coloane ale câmpului. Urmează N linii a câte M caractere ‘X’ și ‘O’ unde ‘X' reprezintă obstacol iar ‘O’ reprezintă zonă liberă.

Ultimele două linii reprezintă codificarea celor două mutări speciale, câte o mutare pe o linie.

Date de ieșire

Fișierul brutar.out va conține, pe prima linie, numărul T de celule al unui traseu de lungime minimă. Următoarele T linii vor conține descrierea traseului, câte o celulă pe o linie, prin coordonatele ei, în ordinea în care au fost parcurse.

Restricții și precizări

• 1 ≤ N, M ≤ 1.000
• 1 ≤ x ≤ N
• 1 ≤ y ≤ M
• Se garantează că mereu va există cel puțin un drum care pornește de pe prima linie și ajunge pe ultima linie a matricei.
• Dacă există mai multe soluții cu număr minim de pași, se poate afișa oricare dintre acestea.

Exemplu

brutar.in

14 10
XXXXXXOXXX
OXOOOXOOOO
OOXXOOXOXO
OXOOOOXXXX
OOOOXXOXOX
OXOXOXXOOO
XOXOOOOXOO
OXXXOXOOOX
XOOXOXOXOO
OXOXOXOXOO
OOOOXXOOXO
XOOOXOXOOX
OXOOOOOOOO
XOXXXOXXXX
2S 1V
2S 1E

brutar.out

9
1 7
3 6
5 7
7 6
9 5
10 5
12 4
12 3
14 2

Explicație

Drumul este colorat în galben:

#include <bits/stdc++.h>

using namespace std;

ifstream cin("brutar.in");
ofstream cout("brutar.out");

int n , m , x , y;
bool a[1001][1001];
int b[1001][1001];
struct poz
{
    int i , j;
};
 poz P[10001] , D[1000001];
queue <poz> Q;

int di[6] = { 0 , 0 , 1 , -1};
int dj[6] = {-1 , 1 , 0 ,  0};

bool inside(int i , int j)
{
    return i >= 1 && j >= 1 && i <= n && j <= m;
}

void lee()
{
    while(!Q.empty())
    {
        poz r;
        r = Q.front();
        for(int i = 0 ; i < 6 ; i++)
        {
            int inou = r.i + di[i];
            int jnou = r.j + dj[i];
            if(inside(inou , jnou) && b[inou][jnou] == 0 && a[inou][jnou] == 1)
            {
                b[inou][jnou] = b[r.i][r.j] + 1;
                Q.push({inou , jnou});
            }
        }
        Q.pop();
    }
}

int main()
{
    cin >> n >> m;
    char s;
    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= m ; j++)
        {
            cin >> s;
            if(s == 'O') a[i][j] = 1;
            else if(s == 'X') a[i][j] = 0;
        }
     cin >> x >> s;
     if(s == 'N') di[4] = -x;
     else if(s == 'S') di[4] = x;
     cin >> x >> s;
     if(s == 'E') dj[4] = x;
     else dj[4] = -x;
     cin >> x >> s;
     if(s == 'N') di[5] = -x;
     else if(s == 'S') di[5] = x;
     cin >> x >> s;
     if(s == 'E') dj[5] = x;
     else dj[5] = -x;
     for(int i = 1 ; i <= m ; i++)
        if(a[1][i] == 1) {Q.push({1 , i});b[1][i] = 1;}
    lee();
    /*for(int i = 1 ; i <= n ; i++)
    {
        for(int j = 1 ; j <= m ; j++)
            cout << b[i][j] << " ";
        cout << '\n';
    }*/
    int mini = 1000000 , pmin = 0;
    for(int i = 1 ; i <= m ; i++)
        if(b[n][i] > 0 && b[n][i] < mini)
        {
            mini = b[n][i];
            pmin = i;
        }
    int i = n , j = pmin , k = mini;
    cout << mini << '\n';
    D[k].i = n , D[k].j = j;
    di[4] = -di[4];
     dj[4] = -dj[4];
     di[5] = -di[5];
     dj[5] = -dj[5];
    while(i != 1)
    {
        for(int d = 0 ; d < 6 ; d++)
        {
            int inou = i + di[d];
            int jnou = j + dj[d];
            if(inside(inou , jnou) && b[inou][jnou] == b[i][j] - 1)
            {
                i = inou;
                j = jnou;
                D[--k] = {i , j};
                break;
            }
        }
    }
    for(int i = 1 ; i <= mini ; i++)
        cout << D[i].i << " " << D[i].j << '\n';
}