Submission #105719

#TimeUsernameProblemLanguageResultExecution timeMemory
105719Pro_ktmrDangerous Skating (JOI16_skating)C++14
100 / 100
555 ms15440 KiB
#include"bits/stdc++.h" using namespace std; #define MP(a,b) make_pair(a,b) int H,W; string S[1000]; int beginY,beginX,endY,endX; vector<int> l[1000],r[1000],u[1000],d[1000]; int cost[1000][1000]; int main(){ cin >> H >> W; for(int i=0; i<H; i++) cin >> S[i]; cin >> beginY >> beginX >> endY >> endX; beginY--; beginX--; endY--; endX--; for(int i=0; i<H; i++){ for(int j=0; j<W; j++){ cost[i][j] = INT_MAX; } } // for(int i=1; i<H-1; i++){ for(int j=1; j<W-1; j++){ if(S[i][j] == '#') continue; if(S[i-1][j] == '#') u[j].push_back(i); if(S[i+1][j] == '#') d[j].push_back(i); if(S[i][j-1] == '#') l[i].push_back(j); if(S[i][j+1] == '#') r[i].push_back(j); } } // priority_queue< pair<int,pair<int,int> > > que; que.push( MP(-0,MP(beginY, beginX)) ); cost[beginY][beginX] = 0; while(!que.empty()){ int y = que.top().second.first; int x = que.top().second.second; int c = -que.top().first; que.pop(); if(S[y-1][x] == '.' && cost[y-1][x] > c+2){ cost[y-1][x] = c+2; que.push( MP(-c-2,MP(y-1, x)) ); } if(S[y+1][x] == '.' && cost[y+1][x] > c+2){ cost[y+1][x] = c+2; que.push( MP(-c-2,MP(y+1, x)) ); } if(S[y][x-1] == '.' && cost[y][x-1] > c+2){ cost[y][x-1] = c+2; que.push( MP(-c-2,MP(y, x-1)) ); } if(S[y][x+1] == '.' && cost[y][x+1] > c+2){ cost[y][x+1] = c+2; que.push( MP(-c-2,MP(y, x+1)) ); } int edge = *(upper_bound(u[x].begin(), u[x].end(), y)-1); if(cost[edge][x] > c+1){ cost[edge][x] = c+1; que.push( MP(-c-1,MP(edge, x)) ); } edge = *lower_bound(d[x].begin(), d[x].end(), y); if(cost[edge][x] > c+1){ cost[edge][x] = c+1; que.push( MP(-c-1,MP(edge, x)) ); } edge = *(upper_bound(l[y].begin(), l[y].end(), x)-1); if(cost[y][edge] > c+1){ cost[y][edge] = c+1; que.push( MP(-c-1,MP(y, edge)) ); } edge = *lower_bound(r[y].begin(), r[y].end(), x); if(cost[y][edge] > c+1){ cost[y][edge] = c+1; que.push( MP(-c-1,MP(y, edge)) ); } } // /*for(int i=0; i<H; i++){ for(int j=0; j<W; j++){ cout << (cost[i][j] == INT_MAX ? -1 : cost[i][j]) << " "; } cout << endl; }*/ if(cost[endY][endX] == INT_MAX) cout << -1 << endl; else cout << cost[endY][endX] << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...