#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast,unroll-loops")
using namespace std;
typedef long long ll;
typedef pair<int, int> pp;
#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define sz(x) (int)x.size()
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define pb push_back
const ll mod = 1e9+7, maxn = 1e3+2, inf = ll(1e9)+5;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int dist_wall[maxn][maxn];
pp ad[maxn][maxn][4];
pp st, en;
bool wall[maxn][maxn];
int n, m;
void clc_bfs_wall(){
deque<pp> q;
rep(i,0,n+2) rep(j,0,m+2) {
dist_wall[i][j] = inf;
if(wall[i][j]) dist_wall[i][j] = 0, q.pb({i, j});
}
while(sz(q)){
auto[i, j] = q.front(); q.pop_front();
rep(d,0,4){
int x = dx[d] + i, y = dy[d] + j;
if(x > 0 && x <= n && y > 0 && y <= m && !wall[x][y] && dist_wall[x][y] == inf)
dist_wall[x][y] = dist_wall[i][j] + 1, q.pb({x, y});
}
}
}
vector<pair<int, pp>> adj(int i, int j){
vector<pair<int, pp>> res;
rep(d,0,4){
int x = dx[d] + i, y = dy[d] + j;
if(x > 0 && x <= n && y > 0 && y <= m && !wall[x][y]) res.pb({1, {x, y}});
}
rep(d,0,4) if(ad[i][j][d].ff + 1) res.pb({dist_wall[i][j], ad[i][j][d]});
return res;
}
void clc_portal_edge(){
rep(i,0,n+2) rep(j,0,m+2) rep(d,0,4) ad[i][j][d] = {-1, -1};
rep(i,0,n+2) rep(j,0,m+2) {
if(wall[i][j]) rep(d,0,4){
int x = i + dx[d], y = j + dy[d];
int a = x, b = y;
while(x > 0 && x <= n && y > 0 && y <= m && !wall[x][y]) ad[x][y][d] = {a, b}, x += dx[d], y += dy[d];
}
}
}
int dijkstra(){
vector<vector<pp>> vc(n*m);
vc[0].pb(st);
vector<vector<int>> dist(n + 2, vector<int>(m + 2, inf)); dist[st.ff][st.ss] = 0;
rep(i,0,sz(vc)){
for(pp c: vc[i]){
if(dist[c.ff][c.ss] - i) continue;
if(c == en) return i;
for(auto[w, p]: adj(c.ff, c.ss)) if(dist[p.ff][p.ss] > i + w)
vc[dist[p.ff][p.ss] = i + w].pb(p);
}
}
return -1;
}
int main(){
cin.tie(0) -> sync_with_stdio(0);
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
cin >> n >> m;
rep(i,0,n+2) rep(j,0,m+2) wall[i][j] = true;
rep(i,1,n+1) rep(j,1,m+1){
char c; cin >> c;
if(c == '#') continue;
if(c == 'S') st = {i, j};
else if(c == 'C') en = {i, j};
wall[i][j] = false;
}
clc_bfs_wall();
clc_portal_edge();
cout << dijkstra() << '\n';
return 0;
}
Compilation message
portals.cpp: In function 'int main()':
portals.cpp:80:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
80 | freopen("in.in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
portals.cpp:81:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
81 | freopen("out.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
596 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
596 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
596 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
596 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
632 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
