#include <iostream> #include <vector> #include <queue> #include <algorithm> #include <array> using namespace std; struct pole { public: int x,y,odleglosc; bool bezpieczne; pole(){bezpieczne = false; x=-1; y=-1; odleglosc = 2000000000;} pole(int wsp_x, int wsp_y, bool bezp) {x=wsp_x; y=wsp_y; odleglosc=2000000000; bezpieczne=bezp;} bool popraw_odl(int nowa_odl) { if (nowa_odl <odleglosc) { odleglosc = nowa_odl; return true; } return false; } }; array<pair<int, int>,4> wsp_sasiedow(int x, int y) { array<pair<int, int>,4> res; res[0]=make_pair(x-1,y); res[1]=make_pair(x+1,y); res[2]=make_pair(x,y-1); res[3]=make_pair(x,y+1); return res; } int main() { std::ios::sync_with_stdio(false); cin.tie(0); int n, m, k; cin>>n >>m >>k; vector<vector<pole>> mapa(n+2, vector<pole>(m+2, pole())); for (int ii=1; ii<n+1; ii++) for(int jj=1; jj<m+1; jj++) { char znak; cin>>znak; if (znak == '.') mapa[ii][jj] = pole(ii,jj,true); else //znak=='X' mapa[ii][jj] = pole(ii,jj,false); } // pole startowe ma wspolrzedne 1,1 // znalezienie najkrotszej sciezki queue<pole*> kolejka; mapa[1][1].popraw_odl(0); kolejka.push(&mapa[1][1]); while (!kolejka.empty()) { pole* obecne_pole = kolejka.front(); kolejka.pop(); if(obecne_pole->bezpieczne) { int x = obecne_pole->x, y= obecne_pole->y; int odl_sasiadow = obecne_pole->odleglosc+1; auto sasiedzi = wsp_sasiedow(x,y); for (int ii=0; ii<4; ii++) { int xx = sasiedzi[ii].first; int yy = sasiedzi[ii].second; if (mapa[xx][yy].bezpieczne) { bool poprawa_odl = mapa[xx][yy].popraw_odl(odl_sasiadow); if (poprawa_odl) kolejka.push(&mapa[xx][yy]); } } } } int najkrotsza_droga = mapa[n][m].odleglosc; int suma_podejsc = n-1 + m-1 +(najkrotsza_droga -(n-1) -(m-1))/2; int suma_spadkow = (najkrotsza_droga -(n-1) -(m-1))/2; // znalezienie czasow przejsc vector<uint64_t> czasy_przejsc(k); for (int ii=0; ii<k; ii++) { uint64_t vgora, vdol, t; cin>>vgora >>vdol; t = vgora *suma_podejsc + vdol *suma_spadkow; czasy_przejsc[ii]=t; } sort(czasy_przejsc.begin(), czasy_przejsc.end()); uint64_t czas_zwyciescy = czasy_przejsc.front(); auto it = upper_bound(czasy_przejsc.begin(), czasy_przejsc.end(), czas_zwyciescy); int liczba_zwyciescow = it-czasy_przejsc.begin(); cout<<czas_zwyciescy<<' '<<liczba_zwyciescow<<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 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 | #include <iostream> #include <vector> #include <queue> #include <algorithm> #include <array> using namespace std; struct pole { public: int x,y,odleglosc; bool bezpieczne; pole(){bezpieczne = false; x=-1; y=-1; odleglosc = 2000000000;} pole(int wsp_x, int wsp_y, bool bezp) {x=wsp_x; y=wsp_y; odleglosc=2000000000; bezpieczne=bezp;} bool popraw_odl(int nowa_odl) { if (nowa_odl <odleglosc) { odleglosc = nowa_odl; return true; } return false; } }; array<pair<int, int>,4> wsp_sasiedow(int x, int y) { array<pair<int, int>,4> res; res[0]=make_pair(x-1,y); res[1]=make_pair(x+1,y); res[2]=make_pair(x,y-1); res[3]=make_pair(x,y+1); return res; } int main() { std::ios::sync_with_stdio(false); cin.tie(0); int n, m, k; cin>>n >>m >>k; vector<vector<pole>> mapa(n+2, vector<pole>(m+2, pole())); for (int ii=1; ii<n+1; ii++) for(int jj=1; jj<m+1; jj++) { char znak; cin>>znak; if (znak == '.') mapa[ii][jj] = pole(ii,jj,true); else //znak=='X' mapa[ii][jj] = pole(ii,jj,false); } // pole startowe ma wspolrzedne 1,1 // znalezienie najkrotszej sciezki queue<pole*> kolejka; mapa[1][1].popraw_odl(0); kolejka.push(&mapa[1][1]); while (!kolejka.empty()) { pole* obecne_pole = kolejka.front(); kolejka.pop(); if(obecne_pole->bezpieczne) { int x = obecne_pole->x, y= obecne_pole->y; int odl_sasiadow = obecne_pole->odleglosc+1; auto sasiedzi = wsp_sasiedow(x,y); for (int ii=0; ii<4; ii++) { int xx = sasiedzi[ii].first; int yy = sasiedzi[ii].second; if (mapa[xx][yy].bezpieczne) { bool poprawa_odl = mapa[xx][yy].popraw_odl(odl_sasiadow); if (poprawa_odl) kolejka.push(&mapa[xx][yy]); } } } } int najkrotsza_droga = mapa[n][m].odleglosc; int suma_podejsc = n-1 + m-1 +(najkrotsza_droga -(n-1) -(m-1))/2; int suma_spadkow = (najkrotsza_droga -(n-1) -(m-1))/2; // znalezienie czasow przejsc vector<uint64_t> czasy_przejsc(k); for (int ii=0; ii<k; ii++) { uint64_t vgora, vdol, t; cin>>vgora >>vdol; t = vgora *suma_podejsc + vdol *suma_spadkow; czasy_przejsc[ii]=t; } sort(czasy_przejsc.begin(), czasy_przejsc.end()); uint64_t czas_zwyciescy = czasy_przejsc.front(); auto it = upper_bound(czasy_przejsc.begin(), czasy_przejsc.end(), czas_zwyciescy); int liczba_zwyciescow = it-czasy_przejsc.begin(); cout<<czas_zwyciescy<<' '<<liczba_zwyciescow<<endl; return 0; } |