Submission #735040

#	Time	Username	Problem	Language	Result	Execution time	Memory
735040		josanneo22	Portals (BOI14_portals)	C++17	0 / 100	17 ms	32032 KiB

portals

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mp make_pair
#define fi first
#define se second 
#define pipii pair<int,pair<int,int>> 
const int maxn=1005;
int n,m,sx,sy,ex,ey;
int ans[maxn][maxn],a[maxn][maxn],up[maxn][maxn],down[maxn][maxn],lf[maxn][maxn],rt[maxn][maxn];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
bool valid(int x,int y){
	if(x>=0 && x<=n-1 && y>=0 && y<=m-1 && a[x][y]==1) return true;
	else return false;
}
signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0); 
	/*
		this task just looks like djikstra, only hard part if to determine
		up,down,lf,rt of each i,j
	*/
	cin>>n>>m;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			char x; cin>>x;
			if(x=='#')a[i][j]=0;
			else a[i][j]=1;

			if(x=='S'){
				sx=i;sy=j;
			}
			if(x=='C'){
				ex=i;ey=j;
			}
		}
	}
	for(int i=0;i<maxn;i++){
		for(int j=0;j<maxn;j++){
			up[i][j]=-1;
			down[i][j]=-1;
			lf[i][j]=-1;
			rt[i][j]=-1;
		}
	} 
	for(int i=0;i<n;i++){
		up[0][i]=0;
		down[n-1][i]=0;
	}
	for(int i=0;i<m;i++){
		rt[i][m-1]=0;
		lf[i][0]=0;
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(a[i][j]==0){
				int tx=i-1,ty=j,ok=1;
				while(tx>=0 && ok){
					if(down[tx][ty]==-1 && a[tx][ty]!=0){
						down[tx][ty]=i-tx;
						tx--;
					}
					else ok=0;
				}
				tx=i+1,ty=j,ok=1;
				while(tx<=n-1 && ok){
					if(up[tx][ty]==-1 && a[tx][ty]!=0){
						up[tx][ty]=tx-i;
						tx++;
					}
					else ok=0;
				}
				tx=i,ty=j+1,ok=1;
				while(ty<=m-1 && ok){
					if(lf[tx][ty]==-1&& a[tx][ty]!=0){
						lf[tx][ty]=ty-j;
						ty++;
					}
					else ok=0;
				}
				tx=i,ty=j-1,ok=1;
				while(ty>=0 && ok){
					if(rt[tx][ty]==-1&& a[tx][ty]!=0){
						rt[tx][ty]=j-ty;
						ty--;
					}
					else ok=0;
				}
			}
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(up[i][j]==-1) up[i][j]=i;
			if(down[i][j]==-1) down[i][j]=n-i-1;
			if(lf[i][j]==-1) lf[i][j]=j;
			if(rt[i][j]==-1) rt[i][j]=m-j-1;
		}
	}
	priority_queue<pipii,vector<pipii>,greater<pipii>> pq;
	pq.push(mp(0,mp(sx,sy)));
	for(int i=0;i<n;i++) for(int j=0;j<m;j++) ans[i][j]=1e9;
	while(pq.size()){
		pair<int,pair<int,int>> u=pq.top(); pq.pop();
		if(!valid(u.se.fi,u.se.se)) continue;
		if(ans[u.se.fi][u.se.se]<=u.fi) continue;
		ans[u.se.fi][u.se.se]=u.fi;
		for(int i=0;i<4;i++){
			if(valid(u.se.fi+dx[i],u.se.se+dy[i])) pq.push(mp(u.fi+1,mp(u.se.fi+dx[i],u.se.se+dy[i])));
		}
		pq.push(mp(u.fi+1,mp(u.se.fi-up[u.se.fi][u.se.se],u.se.se)));
		pq.push(mp(u.fi+1,mp(u.se.fi+down[u.se.fi][u.se.se],u.se.se)));
		pq.push(mp(u.fi+1,mp(u.se.fi,u.se.se-lf[u.se.fi][u.se.se])));
		pq.push(mp(u.fi+1,mp(u.se.fi,u.se.se+rt[u.se.fi][u.se.se])));
	}
	cout<<ans[ex][ey]<<'\n';
}

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