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
#include<iostream>
#include<queue>
#include<vector>

using namespace std;

vector<vector<pair<int,int>>> graph;
char map[2001][2001];
long long results[4'000'002][2];
queue<int> q;
long long n,m,k,result=9'223'372'036'854'775'807,coun=0;

void bfs()
{
    q.push(1);
    while(!q.empty())
    {
        int v=q.front();
        q.pop();
        for(int i=0; i<graph[v].size(); i++)
        {
            if(!results[graph[v][i].first][0])
            {
                if(graph[v][i].second==1)
                {
                    results[graph[v][i].first][0]=results[v][0]+1;
                    results[graph[v][i].first][1]=results[v][1];
                }
                if(graph[v][i].second==2)
                {
                    results[graph[v][i].first][0]=results[v][0];
                    results[graph[v][i].first][1]=results[v][1]+1;
                }
                q.push(graph[v][i].first);
            }
        }
    }
}

int main()
{
    graph.resize(4'000'002);
    cin>>n>>m>>k;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            cin>>map[i][j];
        }
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            if(map[i][j+1]=='.')
            {
                graph[(i-1)*m+j].push_back({(i-1)*m+j+1,1});
            }
            if(map[i+1][j]=='.')
            {
                graph[(i-1)*m+j].push_back({i*m+j,1});
            }
            if(map[i][j-1]=='.')
            {
                graph[(i-1)*m+j].push_back({(i-1)*m+j-1,2});
            }
            if(i>1)
            if(map[i-1][j]=='.')
            {
                graph[(i-1)*m+j].push_back({(i-2)*m+j,2});
            }
        }
    }
    bfs();
    for(int i=0; i<k; i++)
    {
        long long temp, temp2;
        cin>>temp>>temp2;
        if(temp*results[m*n][0]+temp2*results[m*n][1]<result)
        {
            result=temp*results[m*n][0]+temp2*results[m*n][1];
            coun=1;
        }
        else if(temp*results[m*n][0]+temp2*results[m*n][1]==result)
        {
            coun++;
        }
    }
    cout<<result<<" "<<coun;
    return 0;
}