fbpx

Problema #865 – Palat – Rezolvari PBInfo

0

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.

#include <bits/stdc++.h>




using namespace std;

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

#define Inf 100000001
#define Max 1006

struct poz
{
    int i , j;
};

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

int n , m , d[Max][Max];
bool a[Max][Max];

queue < pair<int, poz> >Q;
vector< pair<int, int> > fat;
poz ileana;

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


void lee(int i , int j)
{
    poz x;
    x.i = i;
    x.j = j;
    a[i][j] = 1;
    Q.push(make_pair(0, x));
    while(!Q.empty())
    {
        x = Q.front().second;

        if (Q.front().first < d[x.i][x.j])
            continue;

        for(int i = 0 ; i < 4 ; i++)
        {
            int inou = x.i + di[i];
            int jnou = x.j + dj[i];
            if(inside(inou , jnou) && (d[inou][jnou] > d[x.i][x.j] + 1 || d[inou][jnou] == 0) && a[inou][jnou] != 1)
            {
                poz y;
                y.i = inou;
                y.j = jnou;
                d[inou][jnou] = d[x.i][x.j] + 1;
                Q.push(make_pair(d[inou][jnou], y));
            }
        }
        Q.pop();
    }
}
int main()
{
    char c;
    cin >> n >> m;
    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= m ; j++)
        {
            cin >> c;
            if (c == '_')a[i][j] = 0;
            else if (c == 'Z')a[i][j] = 1;
            else if (c == 'F')
                fat.push_back(make_pair(i, j));
            else
                ileana.i = i, ileana.j = j;
        }

    lee(ileana.i , ileana.j);

    int mindist = Inf;
    poz rez;

    sort(fat.begin(), fat.end());
    for (int i = fat.size() - 1; i >= 0; -- i)
        if (d[fat[i].first][fat[i].second] < mindist && d[fat[i].first][fat[i].second] != 0)
        {
            mindist = d[fat[i].first][fat[i].second];
            rez.i = fat[i].first;
            rez.j = fat[i].second;
        }
    cout << rez.i << ' ' << rez.j;
}
Comentarii
Se incarca comentariile...

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More