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
// tested by Hightail: https://github.com/dj3500/hightail
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define INF 1001001001
#define FOR(i,n) for(int i=0;(i)<(n);++(i))
#define FORI(i,n) for(int i=1;(i)<=(n);++(i))
#define mp make_pair
#define pii pair<int,int>
#define ll long long
#define vi vector<int>
#define SZ(x) ((int)((x).size()))
#define fi first
#define se second
#define wez(n) int n; scanf("%d",&(n));
#define wez2(n,m) int n,m; scanf("%d %d",&(n),&(m));
#define wez3(n,m,k) int n,m,k; scanf("%d %d %d",&(n),&(m),&(k));
inline void pisz(int n) { printf("%d\n",n); }
template<typename T,typename TT> ostream& operator<<(ostream &s,pair<T,TT> t) {return s<<"("<<t.first<<","<<t.second<<")";}
template<typename T> ostream& operator<<(ostream &s,vector<T> t){FOR(i,SZ(t))s<<t[i]<<" ";return s; }
#define DBG(vari) cout<<"["<<__LINE__<<"] "<<#vari<<" = "<<(vari)<<endl;
#define ALL(t) t.begin(),t.end()
#define FOREACH(i,t) for (__typeof(t.begin()) i=t.begin(); i!=t.end(); i++)
#define TESTS wez(testow)while(testow--)
#define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
#define REPD(i,a,b) for(int (i)=(a); (i)>=(b);--i)
#define REMAX(a,b) (a)=max((a),(b));
#define REMIN(a,b) (a)=min((a),(b));
#define IOS ios_base::sync_with_stdio(0);

const int N = 2006;
char s[N][N];
int dist[N][N];

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

int main () {
   wez3(n,m,k)
   FOR(i,n) scanf("%s", s[i]);
   // bfs
   FOR(i,n) FOR(j,m) dist[i][j] = INF;
   dist[0][0] = 0;
   deque<pii> q = {{0,0}};
   while (!q.empty()) {
      int x = q.front().fi, y = q.front().se;
      q.pop_front();
      FOR(d,4) {
         int xx = x + dx[d], yy = y + dy[d];
         if (xx < 0 || xx >= n || yy < 0 || yy >= m) continue;
         if (dist[xx][yy] != INF) continue;
         if (s[xx][yy] == 'X') continue;
         dist[xx][yy] = dist[x][y] + 1;
         q.emplace_back(xx,yy);
      }
   }
   int extraSteps = dist[n-1][m-1] - (n-1+m-1);
   ll up = n-1+m-1 + extraSteps / 2;
   ll down = extraSteps / 2;
   ll best = 1e18;
   int cnt = 0;
   while (k--) {
      wez2(ai,bi);
      ll score = ai * up + bi * down;
      if (score < best) {
         best = score;
         cnt = 1;
      } else if (score == best) {
         ++cnt;
      }
   }
   cout << best << " " << cnt;
}