Profesor Đurić: Haloooo!
Draganče: Dobar dan, profesore, Draganče je ovde.
Profesor Đurić: šta raaadiš, momčino?
Draganče: Upravo šetam parkom, i kad sam stigao do fontane, dobio sam ideju za onaj zadatak o kome smo juče diskutovali...
Profesor Đurić: A jeeee li.

Tako se nastavio telefonski razgovor, koji je trajao K minuta, i ko zna koliko bi još trajao da Dragančetu nije nestalo kredita. Draganče je odmah krenuo da kupi dodatni kredit, pošto zna lokacije svih trafika u parku, i krenuo je u onu do koje mu treba najmanje vremena. čim stigne i uplati kredit, pozvaće profesora ponovo. Profesor Đurić želi da kvalitetno organizuje svoje vreme i potrebna mu je procena koliko Dragančetu treba vremena da ponovo pozove.

Ulaz:

(Ulazni podaci se nalaze u datoteci kredit.in) I Đurić i Draganče tačno znaju mapu parka, koja je data u obliku pravougaone matrice dimenzija N x M, gde su N i M brojevi zadati u prvom redu datoteke. U drugom redu je broj K. U svakom od narednih N redova se nalazi po M znakova, koji označavaju polja na mapi. Dozvoljeni znakovi su 'F', 'x', '.' i 'T'. Znak 'F' označava fontanu. Sve prepreke (npr. jezero, stadion, cveće...) označene su sa 'x', dok su sa '.' označeni delovi parka slobodni za šetnju. Sa 'T' su takođe označeni delovi parka gde se može proći, i u njima se nalazi trafika gde se može uplatiti kredit. Draganče se na početku razgovora nalazi kod fontane. U jednom minutu on može preći u neko od susednih polja (istok, zapad, sever ili jug), a može ostati i tu gde jeste. U toku razgovora on se šeta nasumično. Kada bude krenuo do trafike, neće praviti pauze, već ići najkraćim putem dok ne stigne do nje.

Izlaz:

(Izlazne podatke upisati u datoteku kredit.out) Profesor Đurić ne zna gde se Draganče šetao u toku razgovora i želi da proceni minimalno i maksimalno vreme koje je potrebno Dragančetu da dođe do trafike sa kreditom. U jedinom redu izlazne datoteke treba ispisati dva broja, MIN i MAX, odvojena razmakom; oni označavaju minimalni i maksimalni broj minuta potreban da Draganče stigne do neke od trafika.

Ograničenja:

• brojevi N i M nisu veći od 200
• K nije veće od 500
• broj trafika nije veći od 1000
• znak 'F' se nalazi tačno jednom u ulaznoj datoteci
• Park je takav da Draganče uvek može stići do neke od trafika. U delu sa fontanom se ne nalazi trafika.
• vremensko ograničenje za izvršavanje programa je 1 s.

Napomena:

Ako je barem jedan od brojeva MIN ili MAX tačan, dobićete 50% poena za taj primer.

Primer 1:

5 5
3
x..xF
.x...
T..x.
x.T..
...T.

2 5

Objašnjenje:

Posle 3 minuta razgovora, Draganče će moći da se približi nekoj od trafika i za samo 2 minuta stigne do nje, a moguće je i da ostane sve vreme kraj fontane, odakle će mu trebati 5 minuta do najbliže trafike.

#include <stdio.h>
#include <vector>

using namespace std;

FILE* fin, *fout;

int n, m, k;
char a[200][200];
int startx, starty, n_trafika;

void input() {
     char c;
     fin = fopen("kredit.in", "r");
     fscanf(fin, "%d%d%d%c", &n, &m, &k, &c);

     for (int i = 0; i < n; i++)
          fscanf(fin, "%s", &a[i]);
     fclose(fin);
}

void init() {
     input();
     for (int i = 0; i < n; i++)
         for (int j = 0; j < m; j++) {
             if (a[i][j] == 'F') {
                startx = i; starty = j;
             }
         }
}

bool in(int x, int y) {
     return (x >= 0 && x < n && y >= 0 && y < m && a[x][y] != 'X');
}

void bfs(vector<pair<int, int> > start, int dist[][200], int limit) {
     vector<pair<int, int> > next, now(start);
     for (int i = 0; i < now.size(); i++)
         dist[now[i].first][now[i].second] = 0;
     for (int i = 0; i < limit && !now.empty(); i++) {
         for (int j = 0; j < now.size(); j++) {
             pair<int, int> pos = now[j];
             int x = pos.first, y = pos.second;
             if (in(x+1, y))
                if (dist[x+1][y]==-1) {
                   next.push_back(make_pair(x+1,y));
                   dist[x+1][y] = i+1;
                }
             if (in(x-1, y))
                if (dist[x-1][y]==-1) {
                   next.push_back(make_pair(x-1,y));
                   dist[x-1][y] = i+1;
                }
             if (in(x, y+1))
                if (dist[x][y+1]==-1) {
                   next.push_back(make_pair(x,y+1));
                   dist[x][y+1] = i+1;
                }
             if (in(x, y-1))
                if (dist[x][y-1]==-1) {
                   next.push_back(make_pair(x,y-1));
                   dist[x][y-1] = i+1;
                }
        }
        now.clear();
        next.swap(now);
     }
}

void output(int min, int max) {
     fout = fopen("kredit.out", "w");
     fprintf(fout, "%d %d\n", min, max);
     fclose(fout);
}

int main(int argc, char *argv[])
{
    init();
    int dist1[n][200], dist2[n][200];
    
    vector<pair<int, int> > s;
    s.push_back(make_pair(startx, starty));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            dist1[i][j] = -1;
    bfs(s, dist1, k);
    
    vector<pair<int, int> > t;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            dist2[i][j] = -1;
            if (a[i][j] == 'T')
               t.push_back(make_pair(i, j));
        }
    bfs(t, dist2, 1000000);
    
    int max = 0, min = 1000000;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (dist1[i][j] != -1) {
               if (dist2[i][j] > max) 
                  max = dist2[i][j];
               if (dist2[i][j] < min)
                  min = dist2[i][j];                  
            }
    output(min, max);
    return 0;
}