Submission #98034

#	Time	Username	Problem	Language	Result	Execution time	Memory
98034		dndhk	Dangerous Skating (JOI16_skating)	C++14	100 / 100	691 ms	39584 KiB

skating

#include <bits/stdc++.h>

#define push_back pb
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define F first
#define S second
#define INF 2000000000

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAX_N = 1000;

int N, M;
pii st, ed;
string str[MAX_N+1];
pii L[MAX_N+1][MAX_N+1], U[MAX_N+1][MAX_N+1], D[MAX_N+1][MAX_N+1], R[MAX_N+1][MAX_N+1];

priority_queue<pair<int, pii> > pq;
int dist[MAX_N+1][MAX_N+1];
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};

void check(int x1, int y1, int x2, int y2){
	if(dist[x2][y2] > dist[x1][y1]+1){
		dist[x2][y2] = dist[x1][y1] + 1;
		pq.push({-dist[x2][y2], {x2, y2}});
	}
}

int main(){
	cin>>N>>M;
	for(int i=0; i<N; i++){
		cin>>str[i];
		for(int j=0; j<M; j++){
			dist[i][j] = INF;
		}
	}
	cin>>st.F>>st.S>>ed.F>>ed.S;
	st.F--; st.S--; ed.F--; ed.S--;
	for(int i=0; i<N; i++){
		pii prv;
		for(int j=0; j<M; j++){
			if(str[i][j]=='#')	prv = {i, j+1};
			else	L[i][j] = prv;
		}
		for(int j=M-1; j>=0; j--){
			if(str[i][j]=='#')	prv = {i, j-1};
			else	R[i][j] = prv;
		}
	}
	for(int j=0; j<M; j++){
		pii prv;
		for(int i=0; i<N; i++){
			if(str[i][j]=='#')	prv = {i+1, j};
			else	U[i][j] = prv;
		}
		for(int i=N-1; i>=0; i--){
			if(str[i][j]=='#')	prv = {i-1, j};
			else	D[i][j] = prv;
		}
	}
	dist[st.F][st.S] = 0;
	pq.push({0, st});
	while(!pq.empty()){
		pair<int, pii> now = pq.top(); pq.pop();
		now.F = -now.F;
		if(dist[now.S.F][now.S.S]!=now.F)	continue;
		pii idx = now.S;
		//cout<<now.F<<' '<<idx.F<<' '<<idx.S<<endl;
		if(idx==ed)	break;
		for(int k=0; k<4; k++){
			if(idx.F+dx[k]<0 || idx.F+dx[k]>=N || idx.S+dy[k]<0 || idx.S+dy[k]>=M)	continue;
			if(str[idx.F+dx[k]][idx.S+dy[k]]=='#') continue;
			if(dist[idx.F+dx[k]][idx.S+dy[k]] > dist[idx.F][idx.S] + 2){
				dist[idx.F+dx[k]][idx.S+dy[k]] = dist[idx.F][idx.S]+2;
				pq.push({-dist[idx.F+dx[k]][idx.S+dy[k]], {idx.F+dx[k], idx.S+dy[k]}});
			}
		}
		check(idx.F, idx.S, L[idx.F][idx.S].F, L[idx.F][idx.S].S);
		check(idx.F, idx.S, R[idx.F][idx.S].F, R[idx.F][idx.S].S);
		check(idx.F, idx.S, D[idx.F][idx.S].F, D[idx.F][idx.S].S);
		check(idx.F, idx.S, U[idx.F][idx.S].F, U[idx.F][idx.S].S);
	}
	if(dist[ed.F][ed.S]==INF)	printf("-1");
	else	printf("%d", dist[ed.F][ed.S]);
	return 0;
}

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