#include <bits/stdc++.h> typedef long long ll; using namespace std; bool graph[2005][2005]; int n, m, t; int res; ll top, bot; char c; ll minval = LLONG_MAX, climb; int counter; struct vertex { int x1, x2; int value; }; vertex v; queue<vertex> q; void bfs(vertex x) { graph[x.x1][x.x2] = 1; if(graph[x.x1-1][x.x2] == 0) { graph[x.x1-1][x.x2] = 1; vertex temp = x; temp.value++; temp.x1--; q.push(temp); } if(graph[x.x1+1][x.x2] == 0) { graph[x.x1+1][x.x2] = 1; vertex temp = x; temp.value++; temp.x1++; q.push(temp); } if(graph[x.x1][x.x2-1] == 0) { graph[x.x1][x.x2-1] = 1; vertex temp = x; temp.value++; temp.x2--; q.push(temp); } if(graph[x.x1][x.x2+1] == 0) { graph[x.x1][x.x2+1] = 1; vertex temp = x; temp.value++; temp.x2++; q.push(temp); } return; } int main() { scanf("%d%d%d", &n, &m, &t); for(int i = 0; i<=n+1; i++) { for(int j = 0; j<=m+1; j++) { graph[0][j] = 1; graph[i][0] = 1; graph[n+1][j] = 1; graph[i][m+1] = 1; } } for(int i = 1; i<=n; i++) { for(int j = 1; j<=m; j++) { scanf(" %c", &c); if(c == 'X') { graph[i][j] = 1; } } } v.x1 = 1; v.x2 = 1; v.value = 0; q.push(v); while(!q.empty()){ v = q.front(); q.pop(); bfs(v); if(v.x1 == n && v.x2 == m) { res = v.value; } } climb = (res - n - m + 2)/2 + m + n - 2; for(int i = 1; i<=t; i++) { scanf("%lld%lld", &top, &bot); if(climb * top + (res-climb) * bot == minval) { counter++; } if(climb * top + (res-climb) * bot < minval) { counter = 1; minval = climb * top + (res-climb) * bot; } } printf("%lld %d", minval, counter); }
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 112 113 114 | #include <bits/stdc++.h> typedef long long ll; using namespace std; bool graph[2005][2005]; int n, m, t; int res; ll top, bot; char c; ll minval = LLONG_MAX, climb; int counter; struct vertex { int x1, x2; int value; }; vertex v; queue<vertex> q; void bfs(vertex x) { graph[x.x1][x.x2] = 1; if(graph[x.x1-1][x.x2] == 0) { graph[x.x1-1][x.x2] = 1; vertex temp = x; temp.value++; temp.x1--; q.push(temp); } if(graph[x.x1+1][x.x2] == 0) { graph[x.x1+1][x.x2] = 1; vertex temp = x; temp.value++; temp.x1++; q.push(temp); } if(graph[x.x1][x.x2-1] == 0) { graph[x.x1][x.x2-1] = 1; vertex temp = x; temp.value++; temp.x2--; q.push(temp); } if(graph[x.x1][x.x2+1] == 0) { graph[x.x1][x.x2+1] = 1; vertex temp = x; temp.value++; temp.x2++; q.push(temp); } return; } int main() { scanf("%d%d%d", &n, &m, &t); for(int i = 0; i<=n+1; i++) { for(int j = 0; j<=m+1; j++) { graph[0][j] = 1; graph[i][0] = 1; graph[n+1][j] = 1; graph[i][m+1] = 1; } } for(int i = 1; i<=n; i++) { for(int j = 1; j<=m; j++) { scanf(" %c", &c); if(c == 'X') { graph[i][j] = 1; } } } v.x1 = 1; v.x2 = 1; v.value = 0; q.push(v); while(!q.empty()){ v = q.front(); q.pop(); bfs(v); if(v.x1 == n && v.x2 == m) { res = v.value; } } climb = (res - n - m + 2)/2 + m + n - 2; for(int i = 1; i<=t; i++) { scanf("%lld%lld", &top, &bot); if(climb * top + (res-climb) * bot == minval) { counter++; } if(climb * top + (res-climb) * bot < minval) { counter = 1; minval = climb * top + (res-climb) * bot; } } printf("%lld %d", minval, counter); } |