#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef long double LD; typedef unsigned long long ULL; typedef vector<int> VI; typedef vector<LL> VLL; typedef set<int> SI; typedef pair<int, int> PII; typedef pair<LL, LL> PLL; typedef vector<PII> VPII; typedef vector<PLL> VPLL; const int INF = 1000000001; const LD EPS = 1e-9; const int MOD = 1000000007; const LL LLINF = 1000000000000000001; #define FOR(i, b, e) for(int i = b; i <= e; i++) #define FORD(i, b, e) for(int i = b; i >= e; i--) #define ALL(c) (c).begin(), (c).end() #define SIZE(x) ((int)(x).size()) #define DPRINT(x) cout << #x << ": " << x << endl #define BOOST ios_base::sync_with_stdio(false); cin.tie(nullptr) #define MP make_pair #define PB push_back #define ST first #define ND second #define GGL(x) "Case #" << x << ": " // ゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴ int dirx[] = {-1, 0, 1, 0}; int diry[] = {0, -1, 0, 1}; int dirc = 4; int main() { BOOST; int n, m, k; cin >> n >> m >> k; vector<vector<char>> board(n+2, vector<char>(m+2, 'X')); vector<VI> s(n+2, VI(m+2, -1)); FOR(i, 1, n) FOR(j, 1, m) cin >> board[i][j]; queue<pair<PII, int>> q; q.push(MP(MP(1, 1), 0)); while (!q.empty()) { PII a = q.front().ST; int t = q.front().ND; q.pop(); if (s[a.ST][a.ND] == -1 && board[a.ST][a.ND] == '.') { s[a.ST][a.ND] = t; FOR(d, 0, dirc-1) q.push(MP(MP(a.ST + dirx[d], a.ND + diry[d]), t+1)); } } LL len = s[n][m]; LL bm = (len - m - n + 2) / 2; LL am = len - bm; LL ans = LLINF; LL count = 0; FOR(i, 1, k) { LL a, b; cin >> a >> b; LL val = a * am + b * bm; if (val < ans) { ans = val; count = 1; } else if (val == ans) { count++; } } cout << ans << ' ' << count << '\n'; }
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 95 96 97 | #include <bits/stdc++.h> using namespace std; typedef long long LL; typedef long double LD; typedef unsigned long long ULL; typedef vector<int> VI; typedef vector<LL> VLL; typedef set<int> SI; typedef pair<int, int> PII; typedef pair<LL, LL> PLL; typedef vector<PII> VPII; typedef vector<PLL> VPLL; const int INF = 1000000001; const LD EPS = 1e-9; const int MOD = 1000000007; const LL LLINF = 1000000000000000001; #define FOR(i, b, e) for(int i = b; i <= e; i++) #define FORD(i, b, e) for(int i = b; i >= e; i--) #define ALL(c) (c).begin(), (c).end() #define SIZE(x) ((int)(x).size()) #define DPRINT(x) cout << #x << ": " << x << endl #define BOOST ios_base::sync_with_stdio(false); cin.tie(nullptr) #define MP make_pair #define PB push_back #define ST first #define ND second #define GGL(x) "Case #" << x << ": " // ゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴゴ int dirx[] = {-1, 0, 1, 0}; int diry[] = {0, -1, 0, 1}; int dirc = 4; int main() { BOOST; int n, m, k; cin >> n >> m >> k; vector<vector<char>> board(n+2, vector<char>(m+2, 'X')); vector<VI> s(n+2, VI(m+2, -1)); FOR(i, 1, n) FOR(j, 1, m) cin >> board[i][j]; queue<pair<PII, int>> q; q.push(MP(MP(1, 1), 0)); while (!q.empty()) { PII a = q.front().ST; int t = q.front().ND; q.pop(); if (s[a.ST][a.ND] == -1 && board[a.ST][a.ND] == '.') { s[a.ST][a.ND] = t; FOR(d, 0, dirc-1) q.push(MP(MP(a.ST + dirx[d], a.ND + diry[d]), t+1)); } } LL len = s[n][m]; LL bm = (len - m - n + 2) / 2; LL am = len - bm; LL ans = LLINF; LL count = 0; FOR(i, 1, k) { LL a, b; cin >> a >> b; LL val = a * am + b * bm; if (val < ans) { ans = val; count = 1; } else if (val == ans) { count++; } } cout << ans << ' ' << count << '\n'; } |