Submission #159158

#	Time	Username	Problem	Language	Result	Execution time	Memory
159158		TadijaSebez	Dangerous Skating (JOI16_skating)	C++11	100 / 100	703 ms	217724 KiB

skating

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int inf=1e9+7;
const int N=1050;
const int H=N*N*4;
int n,m;
int ID(int x, int y){ return (x-1)*m+y;}
int U[N][N],D[N][N],L[N][N],R[N][N];
vector<pair<int,int>> E[H];
int dist[H];
bool was[H];
char base[N][N];
int main()
{
	scanf("%i %i",&n,&m);
	for(int i=1;i<=n;i++) scanf("%s",base[i]+1);
	for(int i=1;i<=n;i++)
	{
		for(int j=1,k=1;j<=m;j++)
		{
			if(base[i][j]=='#') k=j+1;
			else L[i][j]=ID(i,k);
		}
		for(int j=m,k=m;j>=1;j--)
		{
			if(base[i][j]=='#') k=j-1;
			else R[i][j]=ID(i,k);
		}
	}
	for(int i=1;i<=m;i++)
	{
		for(int j=1,k=1;j<=n;j++)
		{
			if(base[j][i]=='#') k=j+1;
			else U[j][i]=ID(k,i);
		}
		for(int j=n,k=n;j>=1;j--)
		{
			if(base[j][i]=='#') k=j-1;
			else D[j][i]=ID(k,i);
		}
	}
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(base[i][j]=='.')
	{
		if(base[i][j-1]=='.') E[ID(i,j)].pb({ID(i,j-1),2});
		if(base[i][j+1]=='.') E[ID(i,j)].pb({ID(i,j+1),2});
		if(base[i-1][j]=='.') E[ID(i,j)].pb({ID(i-1,j),2});
		if(base[i+1][j]=='.') E[ID(i,j)].pb({ID(i+1,j),2});
		E[ID(i,j)].pb({L[i][j],1});
		E[ID(i,j)].pb({R[i][j],1});
		E[ID(i,j)].pb({U[i][j],1});
		E[ID(i,j)].pb({D[i][j],1});
	}
	int x,y,a,b;
	scanf("%i %i %i %i",&x,&y,&a,&b);
	if(x==a && y==b) return 0*printf("0\n");
	for(int i=0;i<H;i++) dist[i]=inf;
	queue<int> q[2];
	q[0].push(ID(x,y));
	dist[ID(x,y)]=0;
	while(q[0].size()+q[1].size())
	{
		int u;
		if(q[0].empty() || (q[1].size() && dist[q[1].front()]<dist[q[0].front()]))
		{
			u=q[1].front();
			q[1].pop();
		}
		else
		{
			u=q[0].front();
			q[0].pop();
		}
		if(was[u]) continue;
		was[u]=1;
		for(auto e:E[u])
		{
			int v,w;tie(v,w)=e;
			if(dist[v]>dist[u]+w)
			{
				q[w-1].push(v);
				dist[v]=dist[u]+w;
			}
		}
	}
	int ans=dist[ID(a,b)];
	if(ans==inf) printf("-1\n");
	else printf("%i\n",ans);
	return 0;
}

Compilation message (stderr)

skating.cpp: In function 'int main()':
skating.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
skating.cpp:17:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%s",base[i]+1);
                        ~~~~~^~~~~~~~~~~~~~~~
skating.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i %i %i",&x,&y,&a,&b);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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