#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr);
size_t n, m, k;
cin >> n >> m >> k;
vector<vector<bool>> wall(n, vector<bool>(m));
for(size_t i = 0; i < n; i++)
{
string S;
cin >> S;
for(size_t j = 0; j < m; j++)
wall[i][j] = S[j] == 'X';
}
vector<vector<size_t>> dist(n, vector<size_t>(m, SIZE_MAX));
dist[0][0] = 0;
queue<pair<size_t, size_t>> Q;
Q.emplace(0, 0);
while(not Q.empty())
{
auto [x, y] = Q.front(); Q.pop();
auto maybe = [&](size_t dx, size_t dy) {
if(x+dx < n and y+dy < m and dist[x+dx][y+dy] == SIZE_MAX and not wall[x+dx][y+dy])
dist[x+dx][y+dy] = dist[x][y] + 1, Q.emplace(x+dx, y+dy);
};
maybe(+1, 0); maybe(0, +1);
maybe(-1, 0); maybe(0, -1);
}
uint64_t result = UINT64_MAX, cnt = 0;
auto d0 = n + m - 2, d = dist[n-1][m-1], p = (d - d0) / 2;
while(k --> 0)
{
uint64_t a, b;
cin >> a >> b;
auto v = (d0 + p)*a + p*b;
if(v < result)
result = v, cnt = 0;
cnt += v == result;
}
cout << result << ' ' << cnt << endl;
}
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 | #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); size_t n, m, k; cin >> n >> m >> k; vector<vector<bool>> wall(n, vector<bool>(m)); for(size_t i = 0; i < n; i++) { string S; cin >> S; for(size_t j = 0; j < m; j++) wall[i][j] = S[j] == 'X'; } vector<vector<size_t>> dist(n, vector<size_t>(m, SIZE_MAX)); dist[0][0] = 0; queue<pair<size_t, size_t>> Q; Q.emplace(0, 0); while(not Q.empty()) { auto [x, y] = Q.front(); Q.pop(); auto maybe = [&](size_t dx, size_t dy) { if(x+dx < n and y+dy < m and dist[x+dx][y+dy] == SIZE_MAX and not wall[x+dx][y+dy]) dist[x+dx][y+dy] = dist[x][y] + 1, Q.emplace(x+dx, y+dy); }; maybe(+1, 0); maybe(0, +1); maybe(-1, 0); maybe(0, -1); } uint64_t result = UINT64_MAX, cnt = 0; auto d0 = n + m - 2, d = dist[n-1][m-1], p = (d - d0) / 2; while(k --> 0) { uint64_t a, b; cin >> a >> b; auto v = (d0 + p)*a + p*b; if(v < result) result = v, cnt = 0; cnt += v == result; } cout << result << ' ' << cnt << endl; } |
English