Submission #118422

#	Time	Username	Problem	Language	Result	Execution time	Memory
118422		kig9981	Dangerous Skating (JOI16_skating)	C++17	100 / 100	236 ms	22264 KiB

skating

#include <bits/stdc++.h>

#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif

using namespace std;

const int dx[]={-1,1,0,0}, dy[]={0,0,-1,1};
int N, M, D[1000][1000][4], dist[1000][1000];
vector<string> F;

bool valid_coord(int x, int y)
{
	return 0<=x && x<N && 0<=y && y<M && F[x][y]=='.';
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt","r",stdin));
	TEST(freopen("output.txt","w",stdout));
	TEST(freopen("debug.txt","w",stderr));
	int x, y;
	queue<pair<int,int>> Q[4];
	cin>>N>>M;
	F.resize(N);
	for(int i=0;i<N;i++) cin>>F[i];
	for(int i=0;i<N;i++) {
		D[i][M-1][1]=M-1;
		for(int j=1;j<M;j++) D[i][j][0]=F[i][j-1]=='.' ? D[i][j-1][0]:j;
		for(int j=M-2;j>=0;j--) D[i][j][1]=F[i][j+1]=='.' ? D[i][j+1][1]:j;
	}
	for(int j=0;j<M;j++) {
		D[N-1][j][3]=N-1;
		for(int i=1;i<N;i++) D[i][j][2]=F[i-1][j]=='.' ? D[i-1][j][2]:i;
		for(int i=N-2;i>=0;i--) D[i][j][3]=F[i+1][j]=='.' ? D[i+1][j][3]:i;
	}
	cin>>x>>y;
	memset(dist,0x7f,sizeof(dist));
	dist[--x][--y]=0;
	Q[0].emplace(x,y);
	for(int t=0;Q[t&3].size();t++) while(!Q[t&3].empty()) {
		auto[x,y]=Q[t&3].front();
		Q[t&3].pop();
		if(t!=dist[x][y]) continue;
		for(int k=0;k<4;k++) if(valid_coord(x+dx[k],y+dy[k]) && dist[x+dx[k]][y+dy[k]]>dist[x][y]+2) {
			dist[x+dx[k]][y+dy[k]]=dist[x][y]+2;
			Q[(t+2)&3].emplace(x+dx[k],y+dy[k]);
		}
		if(dist[x][D[x][y][0]]>dist[x][y]+1) {
			dist[x][D[x][y][0]]=dist[x][y]+1;
			Q[(t+1)&3].emplace(x,D[x][y][0]);
		}
		if(dist[x][D[x][y][1]]>dist[x][y]+1) {
			dist[x][D[x][y][1]]=dist[x][y]+1;
			Q[(t+1)&3].emplace(x,D[x][y][1]);
		}
		if(dist[D[x][y][2]][y]>dist[x][y]+1) {
			dist[D[x][y][2]][y]=dist[x][y]+1;
			Q[(t+1)&3].emplace(D[x][y][2],y);
		}
		if(dist[D[x][y][3]][y]>dist[x][y]+1) {
			dist[D[x][y][3]][y]=dist[x][y]+1;
			Q[(t+1)&3].emplace(D[x][y][3],y);
		}
	}
	cin>>x>>y;
	cout<<(dist[--x][--y]==0x7f7f7f7f ? -1:dist[x][y])<<'\n';
	return 0;
}

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