This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//!yrt tsuj uoy srettam gnihton no emoc
#include <bits/stdc++.h>
//#pragma GCC target ("avx2")
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")
using namespace std;
typedef long long ll;
typedef long double ld;
#define um unordered_map
#define pb push_back
#define mp make_pair
#define pii pair <int, int>
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define F first
#define S second
int r, c;
const int N = 1e3 + 2;
pii up[N][N], dw[N][N], le[N][N], ri[N][N];
int mn[N][N], inf = 1e9 + 7;
char s[N][N];
vector <pair <pii, int>> adj[N][N];
int h[N][N];
bool mark[N][N];
set <pair <int, pii>> q;
inline void add_edge(int i, int j){
adj[i][j].pb({dw[i][j], mn[i][j] + 1});
adj[i][j].pb({le[i][j], mn[i][j] + 1});
adj[i][j].pb({ri[i][j], mn[i][j] + 1});
adj[i][j].pb({up[i][j], mn[i][j] + 1});
}
inline void UP(){
for(int i = 0; i < r; i ++){
for(int j = 0; j < c; j ++){
if(i <= 0 || s[i - 1][j] == '#'){
up[i][j] = {i, j};
}else{
up[i][j] = up[i - 1][j];
}
mn[i][j] = min(mn[i][j], abs(i - up[i][j].F));
}
}
}
inline void DOWN(){
for(int i = r - 1; i >= 0; i --){
for(int j = 0; j < c; j ++){
if(i >= r - 1 || s[i + 1][j] == '#'){
dw[i][j] = {i, j};
}else{
dw[i][j] = dw[i + 1][j];
}
mn[i][j] = min(mn[i][j], abs(i - dw[i][j].F));
}
}
}
inline void LEFT(){
for(int j = 0; j < c; j ++){
for(int i = 0; i < r; i ++){
if(j <= 0 || s[i][j - 1] == '#'){
le[i][j] = {i, j};
}else{
le[i][j] = le[i][j - 1];
}
mn[i][j] = min(mn[i][j], abs(j - le[i][j].S));
}
}
}
inline void RIGHT(){
for(int j = c - 1; j >= 0; j --){
for(int i = 0; i < r; i ++){
if(j >= c - 1 || s[i][j + 1] == '#'){
ri[i][j] = {i, j};
}else{
ri[i][j] = ri[i][j + 1];
}
mn[i][j] = min(mn[i][j], abs(j - ri[i][j].S));
}
}
}
inline void dijk(pii v){
q.insert({0, v});
h[v.F][v.S] = 0;
// mark[v.F][v.S] = true;
while(q.size()){
int w = q.begin() -> F;
pii x = q.begin() -> S;
q.erase(q.begin());
// mark[x.F][x.S] = false;
if(w <= h[x.F][x.S]){
for(auto u : adj[x.F][x.S]){
if(h[u.F.F][u.F.S] > h[x.F][x.S] + u.S){
h[u.F.F][u.F.S] = h[x.F][x.S] + u.S;
// if(!mark[u.F.F][u.F.S]){
// mark[u.F.F][u.F.S] = true;
q.insert({h[u.F.F][u.F.S], u.F});
// }
}
}
}
}
}
int main(){
fast_io;
scanf("%d %d", &r, &c);
pii st, en;
for(int i = 0; i < r; i ++){
scanf("%s", &s[i]);
for(int j = 0; j < c; j ++){
if(s[i][j] == 'S'){
st = {i, j};
}
if(s[i][j] == 'C'){
en = {i, j};
}
mn[i][j] = h[i][j] = inf;
}
}
UP();
DOWN();
LEFT();
RIGHT();
for(int i = 0; i < r; i ++){
for(int j = 0; j < c; j ++){
if(i > 0 && s[i - 1][j] != '#'){
adj[i][j].pb({{i - 1, j}, 1});
}
if(i < r - 1 && s[i + 1][j] != '#'){
adj[i][j].pb({{i + 1, j}, 1});
}
if(j > 0 && s[i][j - 1] != '#'){
adj[i][j].pb({{i, j - 1}, 1});
}
if(j < c - 1 && s[i][j + 1] != '#'){
adj[i][j].pb({{i, j + 1}, 1});
}
add_edge(i, j);
}
}
dijk(st);
printf("%d", h[en.F][en.S]);
return 0;
}
Compilation message (stderr)
portals.cpp:4: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
4 | #pragma GCC optimization ("Ofast")
|
portals.cpp:5: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
5 | #pragma GCC optimization ("unroll-loops")
|
portals.cpp: In function 'int main()':
portals.cpp:112:11: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[1002]' [-Wformat=]
112 | scanf("%s", &s[i]);
| ~^ ~~~~~
| | |
| | char (*)[1002]
| char*
portals.cpp:109:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
109 | scanf("%d %d", &r, &c);
| ~~~~~^~~~~~~~~~~~~~~~~
portals.cpp:112:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
112 | scanf("%s", &s[i]);
| ~~~~~^~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |