| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1113366 | LM1 | Portals (BOI14_portals) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 where[N][M][4];
/*
0 left
1 right
2 up
3 down
*/
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;
for(int j=1;j<=m;j++){
if(a[i][j]=='#'){
last=-1;
continue;
}
if(last==-1)last=j;
where[i][j][0]=last;
}
}
for(int i=1;i<=n;i++){
int last=-1;
for(int j=m;j>=1;j--){
if(a[i][j]=='#'){
last=-1;
continue;
}
if(last==-1)last=j;
where[i][j][1]=last;
}
}
for(int j=1;j<=m;j++){
int last=-1;
for(int i=1;i<=n;i++){
if(a[i][j]=='#'){
last=-1;
continue;
}
if(last==-1)last=i;
where[i][j][2]=last;
}
}
for(int j=1;j<=m;j++){
int last=-1;
for(int i=n;i>=1;i--){
if(a[i][j]=='#'){
last=-1;
continue;
}
if(last==-1)last=i;
where[i][j][3]=last;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]=='#')continue;
int l=where[i][j][0];
int r=where[i][j][1];
int u=where[i][j][2];
int d=where[i][j][3];
v[idx[i][l]].pb(idx[i][r]);
v[idx[i][l]].pb(idx[u][j]);
v[idx[i][l]].pb(idx[d][j]);
v[idx[i][r]].pb(idx[i][l]);
v[idx[i][r]].pb(idx[u][j]);
v[idx[i][r]].pb(idx[d][j]);
v[idx[u][j]].pb(idx[i][l]);
v[idx[u][j]].pb(idx[i][r]);
v[idx[u][j]].pb(idx[d][j]);
v[idx[d][j]].pb(idx[i][l]);
v[idx[d][j]].pb(idx[i][r]);
v[idx[d][j]].pb(idx[u][j]);
}
}
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
........
*/