Submission #1111863

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111863		LM1	Portals (BOI14_portals)	C++14	0 / 100	20 ms	24020 KiB

portals

#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)*(m)+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;
	fix[st]=1;
	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;
		}
	}
//	for(int i=1;i<=n1;i++){
//		cout<<(dist[i]==1e9?-1:dist[i])<<" ";
//		if(i%n==0)cout<<"\n";
//	}
	cout<<dist[nd];
}
/*
7 8
########
S.......
#.......
........
C.......
#.......
........
*/

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