// #include <bits/stdc++.h> #include <iostream> #include <set> #include <vector> #include <utility> #include <map> #include <queue> #include <algorithm> #include <string> #include <map> using namespace std; #define PB push_back #define MP make_pair #define F first #define S second typedef long long ll; typedef pair<int, int> pii; const int INF = 1e9; vector<int> dx = { 1, -1, 0, 0 }; vector<int> dy = { 0, 0, 1, -1 }; int n, m, k; vector<string> mapa; vector<vector<bool>> visited; vector<vector<int>> mindist; bool isInRange(int x, int b) { return 0 <= x && x < b; } bool isInBoard(pii p) { return isInRange(p.F, n) && isInRange(p.S, m); } void bfs() { visited.resize(n); mindist.resize(n); for (int i = 0; i < n; i++) { visited[i].resize(m, 0); mindist[i].resize(m, 0); } visited[0][0] = true; queue<pii> q; q.push(MP(0, 0)); while (!q.empty()) { pii el = q.front(); q.pop(); for (int i = 0; i < 4; i++) { pii next = MP(el.F + dx[i], el.S + dy[i]); if (!isInBoard(next) || visited[next.F][next.S]) { continue; } if (mapa[next.F][next.S] == 'X') { continue; } visited[next.F][next.S] = true; mindist[next.F][next.S] = mindist[el.F][el.S] + 1; q.push(next); } } } void solve() { cin >> n >> m >> k; mapa.resize(n); for (int i = 0; i < n; i++) { cin >> mapa[i]; } bfs(); int dist = mindist[n - 1][m - 1]; int mina = (dist + (n + m - 2)) / 2; int minb = dist - mina; int a, b; vector<pii> users(k); for (int i = 0; i < k; i++) { cin >> a >> b; users[i] = MP(a, b); } int minTime = users[0].F * mina + users[0].S * minb; for (pii user: users) { minTime = min(minTime, user.F * mina + user.S * minb); } int ile = 0; for (pii user : users) { if (user.F * mina + user.S * minb == minTime) { ile++; } } cout << minTime << " " << ile << endl; } int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); solve(); 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 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 | // #include <bits/stdc++.h> #include <iostream> #include <set> #include <vector> #include <utility> #include <map> #include <queue> #include <algorithm> #include <string> #include <map> using namespace std; #define PB push_back #define MP make_pair #define F first #define S second typedef long long ll; typedef pair<int, int> pii; const int INF = 1e9; vector<int> dx = { 1, -1, 0, 0 }; vector<int> dy = { 0, 0, 1, -1 }; int n, m, k; vector<string> mapa; vector<vector<bool>> visited; vector<vector<int>> mindist; bool isInRange(int x, int b) { return 0 <= x && x < b; } bool isInBoard(pii p) { return isInRange(p.F, n) && isInRange(p.S, m); } void bfs() { visited.resize(n); mindist.resize(n); for (int i = 0; i < n; i++) { visited[i].resize(m, 0); mindist[i].resize(m, 0); } visited[0][0] = true; queue<pii> q; q.push(MP(0, 0)); while (!q.empty()) { pii el = q.front(); q.pop(); for (int i = 0; i < 4; i++) { pii next = MP(el.F + dx[i], el.S + dy[i]); if (!isInBoard(next) || visited[next.F][next.S]) { continue; } if (mapa[next.F][next.S] == 'X') { continue; } visited[next.F][next.S] = true; mindist[next.F][next.S] = mindist[el.F][el.S] + 1; q.push(next); } } } void solve() { cin >> n >> m >> k; mapa.resize(n); for (int i = 0; i < n; i++) { cin >> mapa[i]; } bfs(); int dist = mindist[n - 1][m - 1]; int mina = (dist + (n + m - 2)) / 2; int minb = dist - mina; int a, b; vector<pii> users(k); for (int i = 0; i < k; i++) { cin >> a >> b; users[i] = MP(a, b); } int minTime = users[0].F * mina + users[0].S * minb; for (pii user: users) { minTime = min(minTime, user.F * mina + user.S * minb); } int ile = 0; for (pii user : users) { if (user.F * mina + user.S * minb == minTime) { ile++; } } cout << minTime << " " << ile << endl; } int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); solve(); return 0; } |