Submission #257448

#	Time	Username	Problem	Language	Result	Execution time	Memory
257448		songc	Dangerous Skating (JOI16_skating)	C++14	100 / 100	417 ms	19696 KiB

skating

#include <bits/stdc++.h>
#define pb push_back
#define lb lower_bound
#define fi first
#define se second
#define mup(a,x) a=min(a,x)
#define Mup(a,x) a=max(a,x)
#define INF 1234567890
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

LL ans;
int N, M, num;
int dx[4]={-1, 0, 1, 0}, dy[4]={0, -1, 0, 1};
int L[1010][1010], R[1010][1010];
int U[1010][1010], D[1010][1010];
bool chk[1010][1010];

struct Data{
	int x, y, w;
	bool operator<(const Data &r)const{return w > r.w;}
};
priority_queue<Data> PQ;

int main(){
	int x1, y1, x2, y2;
	scanf("%d %d", &N, &M);
	for (int i=1; i<=N; i++){
		for (int j=1; j<=M; j++){
			char ch;
			scanf(" %c", &ch);
			chk[i][j] = (ch=='#');
		}
	}
	for (int i=2; i<N; i++) for (int j=2; j<M; j++){
		if (chk[i][j]) continue;
		L[i][j] = chk[i][j-1]?j:L[i][j-1];
		U[i][j] = chk[i-1][j]?i:U[i-1][j];
	}
	for (int i=N-1; i>1; i--) for (int j=M-1; j>1; j--){
		if (chk[i][j]) continue;
		R[i][j] = chk[i][j+1]?j:R[i][j+1];
		D[i][j] = chk[i+1][j]?i:D[i+1][j];
	}
	scanf("%d %d", &x1, &y1);
	scanf("%d %d", &x2, &y2);
	PQ.push((Data){x1, y1, 0});
	while (!PQ.empty()){
		Data t = PQ.top();
		PQ.pop();
		if (chk[t.x][t.y]) continue;
		chk[t.x][t.y] = true;
		if (t.x == x2 && t.y == y2){
			printf("%d\n", t.w);
			return 0;
		}
		if (!chk[t.x][L[t.x][t.y]]) PQ.push((Data){t.x, L[t.x][t.y], t.w+1});
		if (!chk[t.x][R[t.x][t.y]]) PQ.push((Data){t.x, R[t.x][t.y], t.w+1});
		if (!chk[U[t.x][t.y]][t.y]) PQ.push((Data){U[t.x][t.y], t.y, t.w+1});
		if (!chk[D[t.x][t.y]][t.y]) PQ.push((Data){D[t.x][t.y], t.y, t.w+1});
		for (int i=0; i<4; i++) if (!chk[t.x+dx[i]][t.y+dy[i]]) PQ.push((Data){t.x+dx[i], t.y+dy[i], t.w+2});
	}
	puts("-1");
	return 0;
}

Compilation message (stderr)

skating.cpp: In function 'int main()':
skating.cpp:28: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:32:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf(" %c", &ch);
    ~~~~~^~~~~~~~~~~~
skating.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &x1, &y1);
  ~~~~~^~~~~~~~~~~~~~~~~~~
skating.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &x2, &y2);
  ~~~~~^~~~~~~~~~~~~~~~~~~

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