/*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;
vector<bool> used;
int u[1003][1003],d[1003][1003],l[1003][1003],r[1003][1003];
vector<pair<int,int>> g[1010006];
vector<int> dist;
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)
{
g[a].PB(MP(b,d));
}
int main()
{
cin >> n >> m;
k=(m+1)*(n+1);
dist.resize(k+5);
used.resize(k+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]=id(i+1,j);
l[i][j]=id(i,j+1);
}
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]=id(i-1,j);
r[i][j]=id(i,j-1);
}
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;
dist[to]=dist[v]+1;
Q.push(to);
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(a[i][j]=='#')
continue;
if(1)
{
addNode(id(i,j),u[i][j],dist[id(i,j)]+1);
addNode(id(i,j),d[i][j],dist[id(i,j)]+1);
addNode(id(i,j),l[i][j],dist[id(i,j)]+1);
addNode(id(i,j),r[i][j],dist[id(i,j)]+1);
}
}
for(int i=1;i<=k;i++)
{
used[i]=0;
dist[i]=mod;
}
priority_queue<pair<int,int>> q;
q.push(MP(0,st));
dist[st]=0;
int ans=0;
while(!q.empty())
{
int v=-1;
int now=0;
do
{
v=q.top().second;
now=q.top().first;
q.pop();
}while(used[v] && !q.empty());
if(used[v]==1 && v==-1)
break;
used[v]=1;
if(v==en)
{
ans=-now;
break;
}
for(int i=0;i<g[v].size();i++)
{
int to=g[v][i].first;
int D=g[v][i].second;
if(!used[to])
{
q.push(MP(-(D-now),to));
}
}
}
cout<<ans<<endl;
return 0;
}
/*
15 10
.....C....
..........
..........
..........
..........
..........
..........
...S......
..........
..........
..........
..........
..........
..........
..........
*/
Compilation message
portals.cpp: In function 'int main()':
portals.cpp:116: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:143:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[v].size();i++)
~^~~~~~~~~~~~
portals.cpp:198: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 |
Correct |
24 ms |
24056 KB |
Output is correct |
2 |
Correct |
23 ms |
24184 KB |
Output is correct |
3 |
Correct |
23 ms |
24184 KB |
Output is correct |
4 |
Correct |
29 ms |
24184 KB |
Output is correct |
5 |
Correct |
28 ms |
24312 KB |
Output is correct |
6 |
Correct |
24 ms |
24184 KB |
Output is correct |
7 |
Correct |
23 ms |
24284 KB |
Output is correct |
8 |
Correct |
23 ms |
24312 KB |
Output is correct |
9 |
Correct |
23 ms |
24096 KB |
Output is correct |
10 |
Correct |
24 ms |
24184 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
24056 KB |
Output is correct |
2 |
Correct |
23 ms |
24184 KB |
Output is correct |
3 |
Correct |
23 ms |
24312 KB |
Output is correct |
4 |
Correct |
22 ms |
24184 KB |
Output is correct |
5 |
Correct |
24 ms |
24184 KB |
Output is correct |
6 |
Correct |
24 ms |
24192 KB |
Output is correct |
7 |
Correct |
24 ms |
24184 KB |
Output is correct |
8 |
Correct |
24 ms |
24312 KB |
Output is correct |
9 |
Correct |
26 ms |
25080 KB |
Output is correct |
10 |
Correct |
26 ms |
25336 KB |
Output is correct |
11 |
Correct |
25 ms |
25208 KB |
Output is correct |
12 |
Correct |
25 ms |
25080 KB |
Output is correct |
13 |
Correct |
25 ms |
25080 KB |
Output is correct |
14 |
Correct |
24 ms |
24184 KB |
Output is correct |
15 |
Correct |
25 ms |
25080 KB |
Output is correct |
16 |
Correct |
23 ms |
24184 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
24056 KB |
Output is correct |
2 |
Correct |
29 ms |
24184 KB |
Output is correct |
3 |
Correct |
24 ms |
24260 KB |
Output is correct |
4 |
Correct |
23 ms |
24184 KB |
Output is correct |
5 |
Correct |
42 ms |
29476 KB |
Output is correct |
6 |
Correct |
44 ms |
29560 KB |
Output is correct |
7 |
Correct |
43 ms |
29684 KB |
Output is correct |
8 |
Correct |
38 ms |
29860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
24056 KB |
Output is correct |
2 |
Correct |
24 ms |
24232 KB |
Output is correct |
3 |
Correct |
24 ms |
24312 KB |
Output is correct |
4 |
Correct |
24 ms |
24152 KB |
Output is correct |
5 |
Correct |
24 ms |
24276 KB |
Output is correct |
6 |
Correct |
24 ms |
24184 KB |
Output is correct |
7 |
Correct |
23 ms |
24284 KB |
Output is correct |
8 |
Correct |
24 ms |
24184 KB |
Output is correct |
9 |
Correct |
29 ms |
25208 KB |
Output is correct |
10 |
Correct |
32 ms |
25336 KB |
Output is correct |
11 |
Correct |
26 ms |
25080 KB |
Output is correct |
12 |
Correct |
25 ms |
25080 KB |
Output is correct |
13 |
Correct |
25 ms |
25080 KB |
Output is correct |
14 |
Correct |
41 ms |
29372 KB |
Output is correct |
15 |
Correct |
43 ms |
29432 KB |
Output is correct |
16 |
Correct |
44 ms |
29688 KB |
Output is correct |
17 |
Correct |
50 ms |
29784 KB |
Output is correct |
18 |
Correct |
49 ms |
30072 KB |
Output is correct |
19 |
Correct |
45 ms |
31068 KB |
Output is correct |
20 |
Correct |
64 ms |
31832 KB |
Output is correct |
21 |
Correct |
42 ms |
29432 KB |
Output is correct |
22 |
Correct |
43 ms |
29432 KB |
Output is correct |
23 |
Correct |
47 ms |
29688 KB |
Output is correct |
24 |
Correct |
68 ms |
30712 KB |
Output is correct |
25 |
Correct |
28 ms |
24192 KB |
Output is correct |
26 |
Correct |
25 ms |
25080 KB |
Output is correct |
27 |
Correct |
29 ms |
24184 KB |
Output is correct |
28 |
Correct |
48 ms |
29816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
24056 KB |
Output is correct |
2 |
Correct |
24 ms |
24312 KB |
Output is correct |
3 |
Correct |
24 ms |
24312 KB |
Output is correct |
4 |
Correct |
26 ms |
24184 KB |
Output is correct |
5 |
Correct |
24 ms |
24184 KB |
Output is correct |
6 |
Correct |
23 ms |
24184 KB |
Output is correct |
7 |
Correct |
23 ms |
24184 KB |
Output is correct |
8 |
Correct |
24 ms |
24284 KB |
Output is correct |
9 |
Correct |
26 ms |
25208 KB |
Output is correct |
10 |
Correct |
26 ms |
25208 KB |
Output is correct |
11 |
Correct |
25 ms |
25080 KB |
Output is correct |
12 |
Correct |
25 ms |
25080 KB |
Output is correct |
13 |
Correct |
25 ms |
25080 KB |
Output is correct |
14 |
Correct |
41 ms |
29432 KB |
Output is correct |
15 |
Correct |
43 ms |
29432 KB |
Output is correct |
16 |
Correct |
42 ms |
29688 KB |
Output is correct |
17 |
Correct |
44 ms |
29688 KB |
Output is correct |
18 |
Correct |
49 ms |
30072 KB |
Output is correct |
19 |
Correct |
43 ms |
30872 KB |
Output is correct |
20 |
Correct |
53 ms |
31896 KB |
Output is correct |
21 |
Correct |
42 ms |
29560 KB |
Output is correct |
22 |
Correct |
42 ms |
29436 KB |
Output is correct |
23 |
Correct |
44 ms |
29560 KB |
Output is correct |
24 |
Correct |
628 ms |
98904 KB |
Output is correct |
25 |
Correct |
994 ms |
123644 KB |
Output is correct |
26 |
Correct |
514 ms |
128360 KB |
Output is correct |
27 |
Correct |
788 ms |
140740 KB |
Output is correct |
28 |
Correct |
445 ms |
90840 KB |
Output is correct |
29 |
Correct |
469 ms |
91896 KB |
Output is correct |
30 |
Correct |
470 ms |
92868 KB |
Output is correct |
31 |
Correct |
51 ms |
30712 KB |
Output is correct |
32 |
Correct |
817 ms |
124252 KB |
Output is correct |
33 |
Correct |
32 ms |
24184 KB |
Output is correct |
34 |
Correct |
31 ms |
25080 KB |
Output is correct |
35 |
Correct |
535 ms |
104912 KB |
Output is correct |
36 |
Correct |
24 ms |
24184 KB |
Output is correct |
37 |
Correct |
46 ms |
29816 KB |
Output is correct |
38 |
Correct |
376 ms |
98184 KB |
Output is correct |
39 |
Correct |
310 ms |
85008 KB |
Output is correct |