oj.uz

Submission #735043

# Submission time Handle Problem Language Result Execution time Memory
735043 2023-05-03T12:12:55 Z josanneo22 Portals (BOI14_portals) C++17
20 / 100
 39 ms 34316 KB 
#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);  
	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-1;
						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-1;
						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-1;
						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-1;
						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<<ex<<' '<<ey<<'\n';
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cout<<ans[i][j]<<' ';
		}
		cout<<'\n';
	}
	*/
	cout<<ans[ex][ey]<<'\n';
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31956 KB Output is correct
2 Correct 13 ms 31988 KB Output is correct
3 Correct 17 ms 31992 KB Output is correct
4 Correct 13 ms 31964 KB Output is correct
5 Correct 12 ms 31956 KB Output is correct
6 Incorrect 13 ms 31956 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31956 KB Output is correct
2 Correct 13 ms 31956 KB Output is correct
3 Correct 12 ms 32028 KB Output is correct
4 Correct 12 ms 31956 KB Output is correct
5 Correct 13 ms 31956 KB Output is correct
6 Incorrect 12 ms 31956 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 31856 KB Output is correct
2 Correct 13 ms 31944 KB Output is correct
3 Correct 14 ms 31956 KB Output is correct
4 Correct 12 ms 32032 KB Output is correct
5 Correct 29 ms 34240 KB Output is correct
6 Correct 35 ms 34256 KB Output is correct
7 Correct 39 ms 34316 KB Output is correct
8 Correct 18 ms 34132 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31956 KB Output is correct
2 Correct 13 ms 31940 KB Output is correct
3 Correct 14 ms 31980 KB Output is correct
4 Correct 16 ms 31944 KB Output is correct
5 Correct 17 ms 31948 KB Output is correct
6 Incorrect 13 ms 31956 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31900 KB Output is correct
2 Correct 12 ms 31956 KB Output is correct
3 Correct 12 ms 31956 KB Output is correct
4 Correct 12 ms 31956 KB Output is correct
5 Correct 13 ms 32000 KB Output is correct
6 Incorrect 13 ms 31956 KB Output isn't correct
7 Halted 0 ms 0 KB -