#include<cstdio> #include<vector> #include<queue> #include<cstring> #include<climits> const std::vector<std::pair<int, int>> moves = { {-1, 0}, {0, -1}, {0, 1}, {1, 0}}; int main() { int N,M,K; scanf("%d %d %d", &N, &M, &K); char tab[N][M+1]; int distance[N][M+1][2]; for (int i = 0; i < N; ++i) { scanf("%s", tab[i]); } for (int i = 0; i < N; ++i) for (int j = 0; j < M; ++j) { distance[i][j][0] = -1; distance[i][j][1] = -1; } std::queue<std::pair<int, int>> queue; queue.emplace(0, 0); distance[0][0][0] = 0; distance[0][0][1] = 0; while (!queue.empty()) { auto xy = queue.front(); queue.pop(); for (const auto m : moves) { int x = xy.first + m.first, y = xy.second + m.second; if (0 <= x && x < N && 0 <= y && y < M) { if (distance[x][y][0] + distance[x][y][1] != -2 || tab[x][y] != '.') continue; distance[x][y][0] = distance[xy.first][xy.second][0]; distance[x][y][1] = distance[xy.first][xy.second][1]; if (x >= xy.first && y >= xy.second) distance[x][y][0] += 1; else distance[x][y][1] += 1; queue.emplace(x, y); } } } /* for (int i = 0; i < N; ++i) { for (int j = 0; j < M; ++j) printf(" %d:%d", distance[i][j][0], distance[i][j][1]); printf("\n"); }//*/ long long up = distance[N-1][M-1][0]; long long down = distance[N-1][M-1][1]; int a, b; long long min_t = LLONG_MAX; int k = 0; for (int i = 0; i < K; ++i) { scanf("%d %d", &a, &b); long long t = (up * a) + (down * b); //printf("%d: %lld\n", i, t); if (min_t > t) { min_t = t; k = 1; } else if (min_t == t) { k += 1; } } printf("%lld %d\n", min_t, k); return 0; }
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 | #include<cstdio> #include<vector> #include<queue> #include<cstring> #include<climits> const std::vector<std::pair<int, int>> moves = { {-1, 0}, {0, -1}, {0, 1}, {1, 0}}; int main() { int N,M,K; scanf("%d %d %d", &N, &M, &K); char tab[N][M+1]; int distance[N][M+1][2]; for (int i = 0; i < N; ++i) { scanf("%s", tab[i]); } for (int i = 0; i < N; ++i) for (int j = 0; j < M; ++j) { distance[i][j][0] = -1; distance[i][j][1] = -1; } std::queue<std::pair<int, int>> queue; queue.emplace(0, 0); distance[0][0][0] = 0; distance[0][0][1] = 0; while (!queue.empty()) { auto xy = queue.front(); queue.pop(); for (const auto m : moves) { int x = xy.first + m.first, y = xy.second + m.second; if (0 <= x && x < N && 0 <= y && y < M) { if (distance[x][y][0] + distance[x][y][1] != -2 || tab[x][y] != '.') continue; distance[x][y][0] = distance[xy.first][xy.second][0]; distance[x][y][1] = distance[xy.first][xy.second][1]; if (x >= xy.first && y >= xy.second) distance[x][y][0] += 1; else distance[x][y][1] += 1; queue.emplace(x, y); } } } /* for (int i = 0; i < N; ++i) { for (int j = 0; j < M; ++j) printf(" %d:%d", distance[i][j][0], distance[i][j][1]); printf("\n"); }//*/ long long up = distance[N-1][M-1][0]; long long down = distance[N-1][M-1][1]; int a, b; long long min_t = LLONG_MAX; int k = 0; for (int i = 0; i < K; ++i) { scanf("%d %d", &a, &b); long long t = (up * a) + (down * b); //printf("%d: %lld\n", i, t); if (min_t > t) { min_t = t; k = 1; } else if (min_t == t) { k += 1; } } printf("%lld %d\n", min_t, k); return 0; } |