Submission #199589

#	Time	Username	Problem	Language	Result	Execution time	Memory
199589		arnold518	Dangerous Skating (JOI16_skating)	C++14	100 / 100	796 ms	30308 KiB

skating

#include <bits/stdc++.h>
using namespace std;

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

const int MAXN = 1000;
const int INF = 987654321;

struct Queue
{
	int y, x, p, d;
	bool operator < (const Queue &p) const { return d>p.d; }
};

int N, M, SY, SX, EY, EX;
char S[MAXN+10][MAXN+10];
int dist[MAXN+10][MAXN+10][2];
int U[MAXN+10][MAXN+10], D[MAXN+10][MAXN+10], L[MAXN+10][MAXN+10], R[MAXN+10][MAXN+10];

priority_queue<Queue> PQ;
void push(int y, int x, int p, int d)
{
	if(dist[y][x][p]>d) PQ.push({y, x, p, d}), dist[y][x][p]=d;
}

int main()
{
	int i, j;

	scanf("%d%d", &N, &M);
	for(i=1; i<=N; i++) scanf("%s", S[i]+1);
	scanf("%d%d%d%d", &SY, &SX, &EY, &EX);

	for(i=1; i<=N; i++) for(j=1; j<=M; j++)
	{
		if(S[i][j]=='#') U[i][j]=i, L[i][j]=j;
		else U[i][j]=U[i-1][j], L[i][j]=L[i][j-1];
	}
	for(i=N; i>=1; i--) for(j=M; j>=1; j--)
	{
		if(S[i][j]=='#') D[i][j]=i, R[i][j]=j;
		else D[i][j]=D[i+1][j], R[i][j]=R[i][j+1];
	}

	for(i=1; i<=N; i++) for(j=1; j<=M; j++) dist[i][j][0]=dist[i][j][1]=INF;

	push(SY, SX, 0, 0);
	push(SY, SX, 1, 0);
	while(!PQ.empty())
	{
		Queue T=PQ.top(); PQ.pop();
		if(dist[T.y][T.x][T.p]<T.d) continue;
		dist[T.y][T.x][T.p]=T.d;

		if(T.p==0)
		{
			int l, r;
			l=L[T.y][T.x]+1, r=R[T.y][T.x]-1;
			push(T.y, l, 0, T.d+1);
			push(T.y, r, 0, T.d+1);
			if(l<=T.x-1) push(T.y, T.x-1, 0, T.d+2);
			if(T.x+1<=r) push(T.y, T.x+1, 0, T.d+2);
			push(T.y, T.x, 1, T.d);
		}
		else
		{
			int l, r;
			l=U[T.y][T.x]+1, r=D[T.y][T.x]-1;
			push(l, T.x, 1, T.d+1);
			push(r, T.x, 1, T.d+1);
			if(l<=T.y-1) push(T.y-1, T.x, 1, T.d+2);
			if(T.y+1<=r) push(T.y+1, T.x, 1, T.d+2);
			push(T.y, T.x, 0, T.d);
		}
	}
	int ans=min(dist[EY][EX][1], dist[EY][EX][0]);
	if(ans==INF) printf("-1\n");
	else printf("%d\n", ans);
}

Compilation message (stderr)

skating.cpp: In function 'int main()':
skating.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
skating.cpp:33:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=N; i++) scanf("%s", S[i]+1);
                      ~~~~~^~~~~~~~~~~~~~
skating.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d", &SY, &SX, &EY, &EX);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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