This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |