/*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[1001006];
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++)
~^~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
24 ms |
23928 KB |
Output is correct |
2 |
Correct |
24 ms |
24056 KB |
Output is correct |
3 |
Correct |
26 ms |
24076 KB |
Output is correct |
4 |
Correct |
28 ms |
23928 KB |
Output is correct |
5 |
Correct |
33 ms |
24056 KB |
Output is correct |
6 |
Correct |
24 ms |
24028 KB |
Output is correct |
7 |
Correct |
26 ms |
24056 KB |
Output is correct |
8 |
Correct |
23 ms |
24056 KB |
Output is correct |
9 |
Correct |
24 ms |
23928 KB |
Output is correct |
10 |
Correct |
24 ms |
23928 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
23928 KB |
Output is correct |
2 |
Correct |
24 ms |
24056 KB |
Output is correct |
3 |
Correct |
23 ms |
24056 KB |
Output is correct |
4 |
Correct |
24 ms |
23928 KB |
Output is correct |
5 |
Correct |
24 ms |
24056 KB |
Output is correct |
6 |
Correct |
24 ms |
24056 KB |
Output is correct |
7 |
Correct |
24 ms |
24056 KB |
Output is correct |
8 |
Correct |
24 ms |
24056 KB |
Output is correct |
9 |
Correct |
32 ms |
24952 KB |
Output is correct |
10 |
Correct |
26 ms |
25080 KB |
Output is correct |
11 |
Correct |
25 ms |
24824 KB |
Output is correct |
12 |
Correct |
25 ms |
24824 KB |
Output is correct |
13 |
Correct |
25 ms |
24824 KB |
Output is correct |
14 |
Correct |
24 ms |
23928 KB |
Output is correct |
15 |
Correct |
25 ms |
24952 KB |
Output is correct |
16 |
Correct |
25 ms |
23928 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
23800 KB |
Output is correct |
2 |
Correct |
24 ms |
24056 KB |
Output is correct |
3 |
Correct |
24 ms |
24056 KB |
Output is correct |
4 |
Correct |
24 ms |
24032 KB |
Output is correct |
5 |
Correct |
41 ms |
29304 KB |
Output is correct |
6 |
Correct |
44 ms |
29304 KB |
Output is correct |
7 |
Correct |
42 ms |
29560 KB |
Output is correct |
8 |
Correct |
38 ms |
29560 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
24 ms |
23928 KB |
Output is correct |
2 |
Correct |
29 ms |
24056 KB |
Output is correct |
3 |
Correct |
23 ms |
24056 KB |
Output is correct |
4 |
Correct |
24 ms |
23928 KB |
Output is correct |
5 |
Correct |
24 ms |
24188 KB |
Output is correct |
6 |
Correct |
24 ms |
24056 KB |
Output is correct |
7 |
Correct |
24 ms |
24056 KB |
Output is correct |
8 |
Correct |
24 ms |
24056 KB |
Output is correct |
9 |
Correct |
26 ms |
24952 KB |
Output is correct |
10 |
Correct |
26 ms |
24952 KB |
Output is correct |
11 |
Correct |
25 ms |
24952 KB |
Output is correct |
12 |
Correct |
25 ms |
24824 KB |
Output is correct |
13 |
Correct |
26 ms |
24824 KB |
Output is correct |
14 |
Correct |
42 ms |
29304 KB |
Output is correct |
15 |
Correct |
45 ms |
29304 KB |
Output is correct |
16 |
Correct |
42 ms |
29560 KB |
Output is correct |
17 |
Correct |
44 ms |
29432 KB |
Output is correct |
18 |
Correct |
49 ms |
29944 KB |
Output is correct |
19 |
Correct |
42 ms |
30712 KB |
Output is correct |
20 |
Correct |
59 ms |
31768 KB |
Output is correct |
21 |
Correct |
42 ms |
29304 KB |
Output is correct |
22 |
Correct |
41 ms |
29304 KB |
Output is correct |
23 |
Correct |
43 ms |
29432 KB |
Output is correct |
24 |
Correct |
50 ms |
30584 KB |
Output is correct |
25 |
Correct |
23 ms |
23928 KB |
Output is correct |
26 |
Correct |
25 ms |
24824 KB |
Output is correct |
27 |
Correct |
24 ms |
23928 KB |
Output is correct |
28 |
Correct |
38 ms |
29560 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
23928 KB |
Output is correct |
2 |
Correct |
24 ms |
24056 KB |
Output is correct |
3 |
Correct |
24 ms |
24056 KB |
Output is correct |
4 |
Correct |
24 ms |
23928 KB |
Output is correct |
5 |
Correct |
24 ms |
24056 KB |
Output is correct |
6 |
Correct |
24 ms |
24056 KB |
Output is correct |
7 |
Correct |
30 ms |
24056 KB |
Output is correct |
8 |
Correct |
24 ms |
24056 KB |
Output is correct |
9 |
Correct |
25 ms |
24956 KB |
Output is correct |
10 |
Correct |
26 ms |
24952 KB |
Output is correct |
11 |
Correct |
25 ms |
24824 KB |
Output is correct |
12 |
Correct |
26 ms |
25080 KB |
Output is correct |
13 |
Correct |
26 ms |
24936 KB |
Output is correct |
14 |
Correct |
41 ms |
29232 KB |
Output is correct |
15 |
Correct |
43 ms |
29432 KB |
Output is correct |
16 |
Correct |
42 ms |
29432 KB |
Output is correct |
17 |
Correct |
44 ms |
29480 KB |
Output is correct |
18 |
Correct |
49 ms |
29944 KB |
Output is correct |
19 |
Correct |
43 ms |
30664 KB |
Output is correct |
20 |
Correct |
51 ms |
31764 KB |
Output is correct |
21 |
Correct |
47 ms |
29420 KB |
Output is correct |
22 |
Correct |
41 ms |
29304 KB |
Output is correct |
23 |
Correct |
42 ms |
29432 KB |
Output is correct |
24 |
Correct |
620 ms |
99620 KB |
Output is correct |
25 |
Execution timed out |
1080 ms |
124348 KB |
Time limit exceeded |
26 |
Halted |
0 ms |
0 KB |
- |