/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <stack>
#include <cassert>
#include <iterator>
#include <bitset>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;
int n,m,k,st,en,used[1000006],dist[1000006],mot[1000006];
pair<int,int> u[1003][1003],d[1003][1003],l[1003][1003],r[1003][1003];
vector<pair<int,int>> g[1000006];
char a[1003][1003];
int id(int y,int x)
{
return y*m+x;
}
void print(int ind)
{
int y,x;
x=ind%m;
if(!x)
x=m;
y=(ind-x)/m;
cout<<"! "<<y<<" "<<x<<" d="<<dist[ind]<<endl;
}
void addNode(int a,int b,int d)
{
if(a==b)
return;
g[a].PB(MP(b,d));
}
int main()
{
cin >> n >> m;
k=n*m+5;
for(int i=1;i<=n;i++)
{
int x=getchar();
for(int j=1;j<=m;j++)
{
x=getchar();
a[i][j]=(char)x;
if(a[i][j]=='S')
{
st=id(i,j);
a[i][j]='.';
}
else if(a[i][j]=='C')
{
en=id(i,j);
a[i][j]='.';
}
}
}
for(int i=1;i<=n;i++)
a[i][0]=a[i][m+1]='#';
for(int i=1;i<=m;i++)
a[0][i]=a[n+1][i]='#';
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)
{
if(a[i][j]=='#')
u[i][j]=l[i][j]=MP(i,j);
else
{
u[i][j]=u[i-1][j];
l[i][j]=l[i][j-1];
}
}
for(int i=n+1;i>=1;i--)
for(int j=m+1;j>=1;j--)
{
if(a[i][j]=='#')
d[i][j]=r[i][j]=MP(i,j);
else
{
d[i][j]=d[i+1][j];
r[i][j]=r[i][j+1];
}
}
queue<int> Q;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(a[i][j]!='#' && a[i-1][j]=='#' || a[i+1][j]=='#' || a[i][j-1]=='#'|| a[i][j+1]=='#')
{
int start=id(i,j);
Q.push(start);
used[start]=1;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(a[i][j]=='#')
continue;
if(a[i-1][j]!='#')
addNode(id(i,j),id(i-1,j),1);
if(a[i+1][j]!='#')
addNode(id(i,j),id(i+1,j),1);
if(a[i][j-1]!='#')
addNode(id(i,j),id(i,j-1),1);
if(a[i][j+1]!='#')
addNode(id(i,j),id(i,j+1),1);
}
while(!Q.empty())
{
int v=Q.front();
Q.pop();
//print(v);
for(int i=0;i<g[v].size();i++)
{
int to=g[v][i].first;
if(used[to])
continue;
used[to]=1;
mot[to]=mot[v]+1;
Q.push(to);
}
}
for(int i=1;i<=k;i++)
{
used[i]=0;
dist[i]=mod;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(a[i][j]=='#')
continue;
if(1)
{
int y,x;
y=u[i][j].first;
x=u[i][j].second;
addNode(id(i,j),id(y+1,x),mot[id(i,j)]+1);
y=d[i][j].first;
x=d[i][j].second;
addNode(id(i,j),id(y-1,x),mot[id(i,j)]+1);
y=l[i][j].first;
x=l[i][j].second;
addNode(id(i,j),id(y,x+1),mot[id(i,j)]+1);
y=r[i][j].first;
x=r[i][j].second;
addNode(id(i,j),id(y,x-1),mot[id(i,j)]+1);
}
}
priority_queue<pair<int,int>> q;
q.push(MP(0,st));
dist[st]=0;
while(!q.empty())
{
int v=-1;
do
{
v=q.top().second;
q.pop();
}while(used[v] && !q.empty());
if(used[v]==1 && v==-1)
break;
used[v]=1;
//print(v);
for(int i=0;i<g[v].size();i++)
{
int to=g[v][i].first;
int D=g[v][i].second;
if(dist[to]>D+dist[v])
{
dist[to]=D+dist[v];
q.push(MP(-dist[to],to));
}
}
}
cout<<dist[en]<<endl;
return 0;
}
/*
15 10
.....C....
..........
..........
..........
..........
..........
..........
...S......
..........
..........
..........
..........
..........
..........
..........
*/
Compilation message
portals.cpp: In function 'int main()':
portals.cpp:108:29: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if(a[i][j]!='#' && a[i-1][j]=='#' || a[i+1][j]=='#' || a[i][j-1]=='#'|| a[i][j+1]=='#')
~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
portals.cpp:135:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[v].size();i++)
~^~~~~~~~~~~~
portals.cpp:195:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[v].size();i++)
~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
23928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
23800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
23928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
23800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
23900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
