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
//source code for bfs from www.geeksforgeeks.org
#include <bits/stdc++.h>
#include <queue>
#include <iostream>
#include <vector>
struct Point
{
    int x;
    int y;
};
struct queueNode
{
    Point pt;
    int dist;
};

bool isValid(int row, int col, int n, int m)
{
    return (row >= 0) && (row < n) &&
           (col >= 0) && (col < m);
}

int rowNum[] = {-1, 0, 0, 1};
int colNum[] = {0, -1, 1, 0};

int BFS(std::vector<std::vector<int>> mat, Point src, Point dest)
{
    if (!mat[src.x][src.y] || !mat[dest.x][dest.y])
        return -1;

    bool visited[mat.size()][mat[0].size()];
    memset(visited, false, sizeof visited);
    visited[src.x][src.y] = true;
    std::queue<queueNode> q;
    queueNode s = {src, 0};
    q.push(s);
    while (!q.empty())
    {
        queueNode curr = q.front();
        Point pt = curr.pt;
        if (pt.x == dest.x && pt.y == dest.y)
            return curr.dist;
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int row = pt.x + rowNum[i];
            int col = pt.y + colNum[i];
            if (isValid(row, col, mat.size(), mat[0].size()) && mat[row][col] &&
               !visited[row][col])
            {
                visited[row][col] = true;
                queueNode Adjcell = { {row, col},
                                      curr.dist + 1 };
                q.push(Adjcell);
            }
        }
    }
    return -1;
}
int main()
{
    std::ios_base::sync_with_stdio(false);
    int n,m,k;
    std::cin>>n>>m>>k;
    std::vector<std::vector<int>> mat;
    for(int i=0;i<n;++i)
    {
        mat.push_back(std::vector<int>{});
        for(int j=0;j<m;++j)
        {
            char c; std::cin>>c;
            mat[i].push_back((c =='.') ? 1:0);
        }
    }

    Point source = {0, 0};
    Point dest = {n-1, m-1};
    int dist = BFS(mat, source, dest);
    long long  down = (dist-(n+m-2))/2;
    long long up = dist -down;
    long long  min = 1000000000000000000;
    int count =0;
    for(int i=0;i<k;++i)
    {
        int x,y; std::cin>>x>>y;
        long long time = x*up+y*down;
        if(time < min) {min = time ; count =1;}
        else if(time  == min) ++count;
    }

    std::cout << min << " "<<count<<std::endl;

    return 0;
}