oj.uz

Submission #1111861

# Submission time Handle Problem Language Result Execution time Memory
1111861 2024-11-13T07:56:07 Z LM1 Portals (BOI14_portals) C++14
0 / 100
 11 ms 29264 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define ff first
#define ss second
const int N=1e3+5,M=1e6+5;
int n,m,idx[N][N],st,nd,n1,dist[M];
bool fix[M];
char a[N][N];
vector<int>v[M];
int main(){
	ios_base::sync_with_stdio(NULL);cin.tie(NULL);
	cin>>n>>m;n1=n*m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			idx[i][j]=(i-1)*n+j;
			if(a[i][j]=='S')st=idx[i][j];
			if(a[i][j]=='C')nd=idx[i][j];
			//if(a[i][j]!='#')cout<<idx[i][j]<<" ";
			//else cout<<"# ";
		}
		//cout<<"\n";
	}//cout<<"\n";
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]=='#')continue;
			int x=idx[i][j];
			if(i!=1 and a[i-1][j]!='#')v[x].pb(idx[i-1][j]);
			if(j!=1 and a[i][j-1]!='#')v[x].pb(idx[i][j-1]);
			if(i!=n and a[i+1][j]!='#')v[x].pb(idx[i+1][j]);
			if(j!=m and a[i][j+1]!='#')v[x].pb(idx[i][j+1]);
		}
	}
	for(int i=1;i<=n;i++){
		int last=-1;
		a[i][0]=a[i][m+1]='#';
		for(int j=0;j<=m+1;j++){
			if(a[i][j]=='#'){
				if(last==-1)continue;
				int r=j-1;
				if(r-1<=last){
					last=-1;
					continue;
				}
				v[idx[i][last]].pb(idx[i][r]);
				v[idx[i][r]].pb(idx[i][last]);
				//cout<<idx[i][last]<<" "<<idx[i][r]<<"\n";
				last=-1;
			}
			if(last==-1)last=j;
		}
	}
	for(int j=1;j<=m;j++){
		int last=-1;
		a[0][j]=a[n+1][j]='#';
		for(int i=0;i<=n+1;i++){
			if(a[i][j]=='#'){
				if(last==-1)continue;
				int r=i-1;
				if(r-1<=last){
					last=-1;
					continue;
				}
				v[idx[last][j]].pb(idx[r][j]);
				v[idx[r][j]].pb(idx[last][j]);
				//cout<<idx[last][j]<<" "<<idx[r][j]<<"\n";
				last=-1;
			}
			if(last==-1)last=i;
		}
	}
	queue<int>q;
	q.push(st);
	for(int i=1;i<=n1;i++)dist[i]=1e9;
	dist[st]=0;
	while(q.size()){
		int node=q.front();
		//cout<<node<<" ";
		q.pop();
		for(auto i:v[node]){
			if(fix[i])continue;
			dist[i]=dist[node]+1;
			q.push(i);
			fix[i]=1;
		}
	}
	cout<<dist[nd];
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29264 KB Output is correct
2 Correct 6 ms 29264 KB Output is correct
3 Correct 5 ms 27384 KB Output is correct
4 Incorrect 6 ms 27216 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 23888 KB Output is correct
2 Correct 9 ms 24020 KB Output is correct
3 Correct 7 ms 23888 KB Output is correct
4 Incorrect 10 ms 23888 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 23888 KB Output is correct
2 Correct 9 ms 23888 KB Output is correct
3 Correct 11 ms 23944 KB Output is correct
4 Incorrect 10 ms 23888 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 23888 KB Output is correct
2 Correct 7 ms 23876 KB Output is correct
3 Correct 9 ms 23888 KB Output is correct
4 Incorrect 7 ms 23888 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 23888 KB Output is correct
2 Correct 9 ms 23888 KB Output is correct
3 Correct 6 ms 23888 KB Output is correct
4 Incorrect 6 ms 23888 KB Output isn't correct
5 Halted 0 ms 0 KB -