#include<bits/stdc++.h> using namespace std; void visit(int x, int y, int n, int m, vector<vector<int>>& dist, vector<vector<bool>>& field, int d, queue<pair<int, int>>& q){ if(x>= 0 && x < n && y>= 0 && y < m){ if(field[x][y] && dist[x][y] == -1){ dist[x][y] = d; q.push({x, y}); } } } int main(){ int n, m, k; cin>>n>>m>>k; vector<vector<bool>> field(n, vector<bool>(m, true)); for(int i = 0; i < n; i++){ string str; cin>>str; for(int j = 0; j < m; j++){ if(str[j] == 'X')field[i][j] = false; } } vector<vector<int>> dist(n, vector<int>(m, -1)); queue<pair<int, int>> q; dist[0][0] = 0; q.push({0, 0}); while(!q.empty()){ pair<int,int> p = q.front(); q.pop(); int d = dist[p.first][p.second]; int x = p.first; int y = p.second; visit(x-1, y, n, m, dist, field, d+1, q); visit(x+1, y, n, m, dist, field, d+1, q); visit(x, y-1, n, m, dist, field, d+1, q); visit(x, y+1, n, m, dist, field, d+1, q); } int d = dist[n-1][m-1] - n - m +2; vector<long long> playerResult(k); for(int i = 0; i < k; i++){ int a, b; cin>>a>>b; playerResult[i] = 1ll*d/2*a + 1ll*d/2*b + 1ll*(n+m-2)*a; } sort(playerResult.begin(), playerResult.end()); long long minimum = playerResult[0]; int cnt = 1; for(int i = 1; i < k; i++){ if(playerResult[i] == minimum)cnt++; } cout<<minimum<<" "<<cnt; }
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 | #include<bits/stdc++.h> using namespace std; void visit(int x, int y, int n, int m, vector<vector<int>>& dist, vector<vector<bool>>& field, int d, queue<pair<int, int>>& q){ if(x>= 0 && x < n && y>= 0 && y < m){ if(field[x][y] && dist[x][y] == -1){ dist[x][y] = d; q.push({x, y}); } } } int main(){ int n, m, k; cin>>n>>m>>k; vector<vector<bool>> field(n, vector<bool>(m, true)); for(int i = 0; i < n; i++){ string str; cin>>str; for(int j = 0; j < m; j++){ if(str[j] == 'X')field[i][j] = false; } } vector<vector<int>> dist(n, vector<int>(m, -1)); queue<pair<int, int>> q; dist[0][0] = 0; q.push({0, 0}); while(!q.empty()){ pair<int,int> p = q.front(); q.pop(); int d = dist[p.first][p.second]; int x = p.first; int y = p.second; visit(x-1, y, n, m, dist, field, d+1, q); visit(x+1, y, n, m, dist, field, d+1, q); visit(x, y-1, n, m, dist, field, d+1, q); visit(x, y+1, n, m, dist, field, d+1, q); } int d = dist[n-1][m-1] - n - m +2; vector<long long> playerResult(k); for(int i = 0; i < k; i++){ int a, b; cin>>a>>b; playerResult[i] = 1ll*d/2*a + 1ll*d/2*b + 1ll*(n+m-2)*a; } sort(playerResult.begin(), playerResult.end()); long long minimum = playerResult[0]; int cnt = 1; for(int i = 1; i < k; i++){ if(playerResult[i] == minimum)cnt++; } cout<<minimum<<" "<<cnt; } |