Submission #945485

#	Time	Username	Problem	Language	Result	Execution time	Memory
945485		MilosMilutinovic	Dangerous Skating (JOI16_skating)	C++14	100 / 100	341 ms	45344 KiB

skating

#include<bits/stdc++.h>
 
#define pb push_back
#define fi first
#define se second
#define mp make_pair
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
 
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
 
ll readint(){
	ll x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

const int dx[]={1,0,-1,0};
const int dy[]={0,1,0,-1};
int n,m,sx,sy,fx,fy;
int dist[1005][1005];
char s[1005][1005];
pii l[1005][1005],r[1005][1005],u[1005][1005],d[1005][1005];

int main(){
	n=readint(); m=readint();
	for(int i=0;i<n;i++) scanf("%s",s+i);
	sx=readint(); sy=readint();
	fx=readint(); fy=readint();
	--sx; --sy; --fx; --fy;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			dist[i][j]=(int)1e9;
		}
	}
	for(int j=0;j<m;j++){
		for(int i=0;i<n;i++){
			if(j==0||s[i][j]=='#') l[i][j]=mp(i,j+1);
			else l[i][j]=l[i][j-1];
		}
	}
	for(int j=m-1;j>=0;j--){
		for(int i=0;i<n;i++){
			if(j==m-1||s[i][j]=='#') r[i][j]=mp(i,j-1);
			else r[i][j]=r[i][j+1];
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(i==0||s[i][j]=='#') u[i][j]=mp(i+1,j);
			else u[i][j]=u[i-1][j];
		}
	}
	for(int i=n-1;i>=0;i--){
		for(int j=0;j<m;j++){
			if(i==n-1||s[i][j]=='#') d[i][j]=mp(i-1,j);
			else d[i][j]=d[i+1][j];
		}
	}
	dist[sx][sy]=0;
	set<array<int,3>> st;
	st.insert({0,sx,sy});
	while(!st.empty()){
		auto it=st.begin();
		int x=(*it)[1],y=(*it)[2];
		st.erase(it);
		for(auto&p:{l[x][y],r[x][y],u[x][y],d[x][y]}){
			if(p==mp(x,y)) continue;
			int nx=p.fi,ny=p.se;
			if(dist[nx][ny]>dist[x][y]+1){
				dist[nx][ny]=dist[x][y]+1;
				st.insert({dist[nx][ny],nx,ny});
			}
		}
		for(int dir=0;dir<4;dir++){
			int nx=x+dx[dir],ny=y+dy[dir];
			if(s[nx][ny]=='#') continue;
			if(dist[nx][ny]>dist[x][y]+2){
				dist[nx][ny]=dist[x][y]+2;
				st.insert({dist[nx][ny],nx,ny});
			}
		}
	}
	if(dist[fx][fy]==(int)1e9) dist[fx][fy]=-1;
	printf("%d\n",dist[fx][fy]);
	return 0;
}

Compilation message (stderr)

skating.cpp: In function 'int main()':
skating.cpp:35:31: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[1005]' [-Wformat=]
   35 |  for(int i=0;i<n;i++) scanf("%s",s+i);
      |                              ~^  ~~~
      |                               |   |
      |                               |   char (*)[1005]
      |                               char*
skating.cpp:35:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |  for(int i=0;i<n;i++) scanf("%s",s+i);
      |                       ~~~~~^~~~~~~~~~

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