Cerința

Ileana Cosânzeana se mărită. În consecință a dat sfoară-n țară și au venit mai mulți Feți-Frumoși, dornici să primească mâna fetei, împreună cu palatul în care locuiește. Acesta este alcătuit din n*m camere, dispuse sub forma unei matrice cu n linii și m coloane.

În anumite camere nu se poate intra, deoarece acolo se află zmei răi. În celelalte se poate intra; mai precis se poate trece dintr-o cameră în altă cameră dacă se învecinează pe linie sau pe coloană. În una dintre camere se află Ileana Cosânzeana, iar în alte camere se afla câte un Făt-Frumos. Aceștia pot trece dintr-o cameră în alta, cu condiția să nu intre într-o cameră care conține un zmeu. Trecerea dintr-o cameră în alta a unui Făt-Frumos durează un minut.

Alegerea celui care va primi mâna Ilenei se face pe principiul primul venit, primul servit (suntem la capitolul Coada). Mai precis, se va căsători cu Ileana Cosânzeana acel Făt Frumos care ajunge primul la ea. Dacă ajung la Ileana Cosânzeana mai mulți Feți-Frumoși în același timp, deoarece este interzisă poligamia, Ileana se va căsători cu Făt-Frumos care la început era situat cât mai jos (pe o linie cu indice cât mai mare). Dacă mai mulți Feți-Frumoși situați pe aceeași linie ajung în timp minim la Ileana, aceasta se va căsători cu cel care era cât mai la dreapta (pe o coloană cu indice cât mai mare).

Aflați poziția inițială a lui Făt-Frumos care va primi mâna fetei.

Date de intrare

Fișierul de intrare palat.in conține pe prima linie numerele n m, iar următoarele n linii câte m caractere, care pot fi:

Z – reprezintă o cameră ocupată de un zmeu
I – reprezintă camera în care se află Ileana Cosânzeana
F – reprezinta o cameră în care se flă un Făt-Frumos
_ – reprezintă o cameră liberă

Date de ieșire

Fișierul de ieșire palat.out va conține pe prima linie două numere i j, separate prin exact un spațiu, reprezentând coordonatele (linie coloană) ale camerei în care se afla acel Făt-Frumos care va primi mâna Ilenei.

Restricții și precizări

1 ≤ n ≤ 1000
1 ≤ m ≤ 1000
liniile și coloanele sunt numerotate de la 1

Exemplu

palat.in

4 5
ZF_ZF
_Z_Z_
_I___
_Z_ZF

palat.out

4 5

Explicație

În palat se află trei Feți Frumoși. Doi dintre ei ajung la Ileana Cosânzeana în 3 minute, al treilea în 4 minute.

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 Palat:

#include <iostream>
#include <fstream>
#include <cassert>
using namespace std;

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

int n , m;
int a[1001][1001];
short x[1000001], y[1000001];
char P[1001][1001];

const int dx[]={0 , 0 , 1 , -1}, dy[]={1 , -1 , 0 , 0};

int main(){
    fin >> n >> m;
    for(int i = 1 ; i <= n ; i ++)
        for(int j = 1 ; j <= m ; j ++)
        {
            fin >> P[i][j];
            if(P[i][j] == 'I')
                x[1] = i, y[1] = j , cerr << i << " " << j;
        }
    
    fin.close();
    
    int st , dr;
    st = dr = 1;
    a[x[1]][y[1]] = 1;
    while(st <= dr)
    {
        int i = x[st], j = y[st];
        for(int k = 0 ; k < 4 ; k ++)
        {
            int ii = i + dx[k], jj = j + dy[k];
            if( ii > 0 && ii <= n && jj > 0 && jj <= m && P[ii][jj] !='Z' && a[ii][jj] == 0)
            {
                a[ii][jj] = a[i][j] + 1;
                dr ++;
                x[dr] = ii, y[dr] = jj;
            }
        }
        st ++;
    }
    /*
    for(int i = 1 ; i <= n ; i ++)
    {
        for(int j = 1 ; j <= m ; j ++)
            cerr << a[i][j] << " ";
        cerr << endl;
    }
    */
    int Min = 1000000000 , imin ,jmin;
    for(int i = 1 ; i <= n ; i ++)
        for(int j = 1 ; j <= m ; j ++)
            if( P[i][j] == 'F' && a[i][j] <= Min && a[i][j] > 0)
                Min = a[i][j] , imin = i , jmin = j;
    fout << imin << " " << jmin;
    fout.close();
    return 0;
}

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 #865 Palat

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #865 Palat 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 #865 Palat