#include <iostream> #include <vector> #include <map> using namespace std; #define N = 2000; int n=5, m=7, k=1; short mapa[2000][2000]; long long trasa[2000][2000]; long long uptime=2, downtime=1; long long findPath(long long time,int x, int y, short direct) { if (x == n - 1 && y == m - 1) { return time; } if (trasa[x][y] > 0) return trasa[x][y]; trasa[x][y] = -1; long long t = 0, d = 0, l = 0, r = 0, dmax = 0; if (direct != 2 && x < n - 1 && mapa[x + 1][y] == 0 && trasa[x + 1][y] >= 0) { t = findPath(uptime+time, x + 1, y, 0); if (t > dmax) dmax = t; } if (direct != 0 && x > 0 && mapa[x-1][y] == 0 && trasa[x -1][y] >= 0) { d = findPath(downtime + time, x - 1, y,2); if (d > dmax) dmax = d; } if (direct != 3 && y < m - 1 && mapa[x][y+1] == 0 && trasa[x ][y+1] >= 0) { r = findPath(uptime+time, x, y+1,1); if (r > dmax) dmax = r; } if (direct != 1 && y > 0 && mapa[x][y-1] == 0 && trasa[x][y-1] >= 0) { l = findPath(downtime+time, x, y-1,3); if (l > dmax) dmax = l; } trasa[x][y] = dmax; return dmax; } int main() { cin >> n >> m >> k; char c; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> c; mapa[i][j] = (c == 'X') ? 1 : 0; } } long long sum = 0, min = -1; int ludzie = 0; map <pair<int, int>, long long> czasy; while (k--) { cin >> uptime >> downtime; if (czasy.find(make_pair(uptime, downtime)) == czasy.end()) { for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { trasa[i][j] = 0; } } sum = findPath(0, 0, 0, 0); czasy[make_pair(uptime, downtime)] = sum; } else { sum = czasy[make_pair(uptime, downtime)]; } if (sum < min || min == -1) { min = sum; ludzie = 1; } else { if (sum == min) { ludzie++; } } //cout << "Typ: " << k << endl; //for (int i = 0; i < n; i++) { // for (int j = 0; j < m; j++) { // cout << trasa[i][j] << " "; // } // cout << endl; //} } cout << min << " " << ludzie << endl; 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 | #include <iostream> #include <vector> #include <map> using namespace std; #define N = 2000; int n=5, m=7, k=1; short mapa[2000][2000]; long long trasa[2000][2000]; long long uptime=2, downtime=1; long long findPath(long long time,int x, int y, short direct) { if (x == n - 1 && y == m - 1) { return time; } if (trasa[x][y] > 0) return trasa[x][y]; trasa[x][y] = -1; long long t = 0, d = 0, l = 0, r = 0, dmax = 0; if (direct != 2 && x < n - 1 && mapa[x + 1][y] == 0 && trasa[x + 1][y] >= 0) { t = findPath(uptime+time, x + 1, y, 0); if (t > dmax) dmax = t; } if (direct != 0 && x > 0 && mapa[x-1][y] == 0 && trasa[x -1][y] >= 0) { d = findPath(downtime + time, x - 1, y,2); if (d > dmax) dmax = d; } if (direct != 3 && y < m - 1 && mapa[x][y+1] == 0 && trasa[x ][y+1] >= 0) { r = findPath(uptime+time, x, y+1,1); if (r > dmax) dmax = r; } if (direct != 1 && y > 0 && mapa[x][y-1] == 0 && trasa[x][y-1] >= 0) { l = findPath(downtime+time, x, y-1,3); if (l > dmax) dmax = l; } trasa[x][y] = dmax; return dmax; } int main() { cin >> n >> m >> k; char c; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> c; mapa[i][j] = (c == 'X') ? 1 : 0; } } long long sum = 0, min = -1; int ludzie = 0; map <pair<int, int>, long long> czasy; while (k--) { cin >> uptime >> downtime; if (czasy.find(make_pair(uptime, downtime)) == czasy.end()) { for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { trasa[i][j] = 0; } } sum = findPath(0, 0, 0, 0); czasy[make_pair(uptime, downtime)] = sum; } else { sum = czasy[make_pair(uptime, downtime)]; } if (sum < min || min == -1) { min = sum; ludzie = 1; } else { if (sum == min) { ludzie++; } } //cout << "Typ: " << k << endl; //for (int i = 0; i < n; i++) { // for (int j = 0; j < m; j++) { // cout << trasa[i][j] << " "; // } // cout << endl; //} } cout << min << " " << ludzie << endl; return 0; } |