#include <bits/stdc++.h> int n, m, k; int a, b; long long int wynik; int ile; int dl, kr; char s[2003]; int odl[2003][2003]; bool mapa[2003][2003]; int X[]={1, 0, -1, 0}; int Y[]={0, 1, 0, -1}; bool istnieje(int x, int y) { if(1<=x && x<=n && 1<=y && y<=m && mapa[x][y]==false) return true; return false; } void BFS() { std::queue<std::pair<int, int> > q; q.push({1, 1}); odl[1][1]=0; while(q.size()>0) { int x=q.front().first; int y=q.front().second; q.pop(); for(int l=0; l<4; l++) { int xx=x+X[l]; int yy=y+Y[l]; if(istnieje(xx, yy) && odl[xx][yy]<0) { odl[xx][yy]=odl[x][y]+1; q.push({xx, yy}); } } } } int main() { scanf("%d%d%d", &n, &m, &k); for(int i=1; i<=n; i++) { scanf("%s", s); for(int j=1; j<=m; j++) if(s[j-1]=='X') mapa[i][j]=true; } for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) odl[i][j]=-1; BFS(); dl=n+m-2; kr=(odl[n][m]-dl)/2; dl+=kr; wynik=(long long)(1000000000)*(1000000000); for(int i=1; i<=k; i++) { scanf("%d%d", &a, &b); if((long long)a*dl+(long long)b*kr<wynik) { wynik=(long long)a*dl+(long long)b*kr; ile=0; } if((long long)a*dl+(long long)b*kr==wynik) ile++; } printf("%lld %d\n", wynik, ile); }
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 | #include <bits/stdc++.h> int n, m, k; int a, b; long long int wynik; int ile; int dl, kr; char s[2003]; int odl[2003][2003]; bool mapa[2003][2003]; int X[]={1, 0, -1, 0}; int Y[]={0, 1, 0, -1}; bool istnieje(int x, int y) { if(1<=x && x<=n && 1<=y && y<=m && mapa[x][y]==false) return true; return false; } void BFS() { std::queue<std::pair<int, int> > q; q.push({1, 1}); odl[1][1]=0; while(q.size()>0) { int x=q.front().first; int y=q.front().second; q.pop(); for(int l=0; l<4; l++) { int xx=x+X[l]; int yy=y+Y[l]; if(istnieje(xx, yy) && odl[xx][yy]<0) { odl[xx][yy]=odl[x][y]+1; q.push({xx, yy}); } } } } int main() { scanf("%d%d%d", &n, &m, &k); for(int i=1; i<=n; i++) { scanf("%s", s); for(int j=1; j<=m; j++) if(s[j-1]=='X') mapa[i][j]=true; } for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) odl[i][j]=-1; BFS(); dl=n+m-2; kr=(odl[n][m]-dl)/2; dl+=kr; wynik=(long long)(1000000000)*(1000000000); for(int i=1; i<=k; i++) { scanf("%d%d", &a, &b); if((long long)a*dl+(long long)b*kr<wynik) { wynik=(long long)a*dl+(long long)b*kr; ile=0; } if((long long)a*dl+(long long)b*kr==wynik) ile++; } printf("%lld %d\n", wynik, ile); } |