제출 #199443

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
199443		TadijaSebez	포탈들 (BOI14_portals)	C++11	100 / 100	387 ms	29164 KiB

portals

#include <bits/stdc++.h>
using namespace std;
const int N=1050;
char base[N][N];
int wd[N][N],U[N][N],D[N][N],L[N][N],R[N][N];
int mv[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int dist[N][N];
int main(){
	int n,m,sx,sy,ex,ey;
	scanf("%i %i",&n,&m);
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)wd[i][j]=min({i,j,n-i+1,m-j+1});
	queue<int> q;
	for(int i=1;i<=n;i++){
		scanf("%s",base[i]+1);
		for(int j=1;j<=m;j++){
			if(base[i][j]=='S'){
				sx=i,sy=j;
				base[i][j]='.';
			}else if(base[i][j]=='C'){
				ex=i,ey=j;
				base[i][j]='.';
			}else if(base[i][j]=='#'){
				wd[i][j]=0;
				q.push(i*N+j);
			}
		}
	}
	while(q.size()){
		int x=q.front()/N;
		int y=q.front()%N;
		q.pop();
		for(int k=0;k<4;k++){
			int i=x+mv[k][0];
			int j=y+mv[k][1];
			if(base[i][j]=='.'){
				if(wd[i][j]>wd[x][y]+1){
					wd[i][j]=wd[x][y]+1;
					q.push(i*N+j);
				}
			}
		}
	}
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)U[i][j]=base[i-1][j]=='.'?U[i-1][j]:i*N+j,L[i][j]=base[i][j-1]=='.'?L[i][j-1]:i*N+j;
	for(int i=n;i>=1;i--)for(int j=m;j>=1;j--)D[i][j]=base[i+1][j]=='.'?D[i+1][j]:i*N+j,R[i][j]=base[i][j+1]=='.'?R[i][j+1]:i*N+j;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)dist[i][j]=1e9;
	dist[sx][sy]=0;
	priority_queue<pair<int,int>> pq;
	pq.push({-dist[sx][sy],sx*N+sy});
	auto Try=[&](int x,int y,int d){
		if(dist[x][y]>d){
			dist[x][y]=d;
			pq.push({-dist[x][y],x*N+y});
		}
	};
	while(pq.size()){
		int x=pq.top().second/N;
		int y=pq.top().second%N;
		int d=-pq.top().first;
		pq.pop();
		if(d!=dist[x][y])continue;
		for(int k=0;k<4;k++){
			int i=x+mv[k][0];
			int j=y+mv[k][1];
			if(base[i][j]=='.'){
				Try(i,j,dist[x][y]+1);
			}
		}
		Try(U[x][y]/N,U[x][y]%N,dist[x][y]+wd[x][y]);
		Try(D[x][y]/N,D[x][y]%N,dist[x][y]+wd[x][y]);
		Try(L[x][y]/N,L[x][y]%N,dist[x][y]+wd[x][y]);
		Try(R[x][y]/N,R[x][y]%N,dist[x][y]+wd[x][y]);
	}
	printf("%i\n",dist[ex][ey]);
	return 0;
}

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

portals.cpp: In function 'int main()':
portals.cpp:10:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
portals.cpp:14:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",base[i]+1);
   ~~~~~^~~~~~~~~~~~~~~~
portals.cpp:73:8: warning: 'ey' may be used uninitialized in this function [-Wmaybe-uninitialized]
  printf("%i\n",dist[ex][ey]);
  ~~~~~~^~~~~~~~~~~~~~~~~~~~~
portals.cpp:73:8: warning: 'ex' may be used uninitialized in this function [-Wmaybe-uninitialized]
portals.cpp:48:29: warning: 'sy' may be used uninitialized in this function [-Wmaybe-uninitialized]
  pq.push({-dist[sx][sy],sx*N+sy});
                         ~~~~^~~
portals.cpp:48:27: warning: 'sx' may be used uninitialized in this function [-Wmaybe-uninitialized]
  pq.push({-dist[sx][sy],sx*N+sy});
                         ~~^~

• Subtask 1: 11 / 11
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 19 / 19
• Subtask 5: 30 / 30