제출 #159157

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
159157		TadijaSebez	Dangerous Skating (JOI16_skating)	C++11	100 / 100	1033 ms	210364 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;}
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 E[ID(i,j)].pb({ID(i,k),1});
		}
		for(int j=m,k=m;j>=1;j--)
		{
			if(base[i][j]=='#') k=j-1;
			else E[ID(i,j)].pb({ID(i,k),1});
		}
	}
	for(int i=1;i<=m;i++)
	{
		for(int j=1,k=1;j<=n;j++)
		{
			if(base[j][i]=='#') k=j+1;
			else E[ID(j,i)].pb({ID(k,i),1});
		}
		for(int j=n,k=n;j>=1;j--)
		{
			if(base[j][i]=='#') k=j-1;
			else E[ID(j,i)].pb({ID(k,i),1});
		}
	}
	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});
	}
	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<pair<int,int>> q[2];
	q[0].push({ID(x,y),0});
	dist[ID(x,y)]=0;
	while(q[0].size()+q[1].size())
	{
		int u,d;
		if(q[0].empty() || (q[1].size() && q[1].front().second<q[0].front().second))
		{
			tie(u,d)=q[1].front();
			q[1].pop();
		}
		else
		{
			tie(u,d)=q[0].front();
			q[0].pop();
		}
		if(dist[u]!=d) continue;
		for(auto e:E[u])
		{
			int v,w;tie(v,w)=e;
			if(dist[v]>dist[u]+w)
			{
				dist[v]=dist[u]+w;
				q[w-1].push({v,dist[v]});
			}
		}
	}
	int ans=dist[ID(a,b)];
	if(ans==inf) printf("-1\n");
	else printf("%i\n",ans);
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

skating.cpp: In function 'int main()':
skating.cpp:15: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:16: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:51: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