1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2007;
bool odwiedzony[MAXN][MAXN];
int warstwa[MAXN][MAXN];
int dx[] = {0, 0, -1, 1}, dy[] = {1, -1, 0, 0};
queue <pair <int, int> > Q;

vector <pair <int, int> >dane;
vector <long long> wyniki;



int x,y;
bool bezpiecznie[10020][10020];
int liczba_wie, liczba_kol, liczba_uczestnikow;
char czar;
int minimalny_wynik;
int main () {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>liczba_kol>>liczba_wie>>liczba_uczestnikow;
    minimalny_wynik=liczba_kol+liczba_wie-2;

    for (int i=1; i<=liczba_kol; i++) {
        for (int k=1; k<=liczba_wie; k++) {
            cin>>czar;
            if (czar=='.')
                bezpiecznie[i][k]=1;
            else if (czar=='X')
                bezpiecznie[i][k]=0;
            } }

    for (int i=0;i<liczba_uczestnikow; i++) {
        cin>>x>>y;
        dane.push_back(make_pair(x,y)); }

    //for (int i=1; i<=liczba_kol; i++) {
       // for (int k=1; k<=liczba_wie; k++) {
       //     cout<<bezpiecznie[i][k]<<" "; }
   // cout<<endl; }

    queue <pair <int, int> > Q;
	Q.push(make_pair(1,1));
	odwiedzony[1][1] = true;
	//cout<<" Wie:"<<Q.front().first<<"  kol:"<<Q.front().second<<endl;

	while (not(Q.empty())) {
  		int wie = Q.front().first;
  		int kol = Q.front().second;
  	    Q.pop();
  		for (int d=0; d<4; d++) {
    		auto sasiad = make_pair(wie+dx[d], kol+dy[d]);
    		if (1 <= sasiad.second and sasiad.second <= liczba_wie and bezpiecznie[sasiad.first][sasiad.second]==1 and 1 <= sasiad.first and sasiad.first <= liczba_kol) {
                if (not(odwiedzony[sasiad.first][sasiad.second])) {
                    odwiedzony[sasiad.first][sasiad.second] = true;
                    Q.push(sasiad);
      //              cout<<" wie:"<<sasiad.first<<"  kol:"<<sasiad.second<<"   "<<endl;
                    warstwa[sasiad.first][sasiad.second] = warstwa[wie][kol] + 1;
                }
            }

        }
    }
  /*  cout<<endl<<endl<<endl;

    for (int i=1; i<=liczba_kol; i++) {
        for (int k=1; k<=liczba_wie; k++) {
            cout<<warstwa[i][k]<<" "; }
   // cout<<endl;
    */
   // }

    //cout<<"\n \n \n \n \n";
    int a =minimalny_wynik+(warstwa[liczba_kol][liczba_wie]-minimalny_wynik)/2;
    int b= (warstwa[liczba_kol][liczba_wie]-minimalny_wynik)/2;

    long long najmniejszy=INT_MAX;

    long long rezultat;
    for (int i=0; i<dane.size(); i++) {
        rezultat=dane[i].first*a + dane[i].second*b;
        if (rezultat<=najmniejszy) {
            najmniejszy=rezultat;
            wyniki.push_back(rezultat);  }


    }

    sort(wyniki.begin(), wyniki.end());

    int ost=wyniki[0];
    int ile_takich=0;
    for (int i=0; i<wyniki.size(); i++)  {
        if (wyniki[i]==ost)
            ile_takich++;
        else
            break; }

    cout<<wyniki[0]<<" "<<ile_takich;

    //cout<<"A: "<<a<<" B:"<<b;
}