Submission #105719

#	Time	Username	Problem	Language	Result	Execution time	Memory
105719		Pro_ktmr	Dangerous Skating (JOI16_skating)	C++14	100 / 100	555 ms	15440 KiB

skating

#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;
}

• Subtask 1: 13 / 13
• Subtask 2: 65 / 65
• Subtask 3: 22 / 22