This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/* [Author: Nguyen Ngoc Hung] - From THPT Ngo Gia Tu with Love */
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <locale>
#include <map>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <unordered_set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <utility>
#include <valarray>
#include <vector>
#include <cstring>
#include <unordered_map>
#include <cmath>
#include <array>
#include <cassert>
#include <random>
#include <chrono>
using namespace std;
#define __nnhzzz__ signed main()
#define BIT(i,j) ((i>>j)&1LL)
#define MASK(i) (1LL<<i)
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) (int)(x).size()
#define _PB push_back
#define fi first
#define se second
#define ll long long
#define ld long double
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define pii pair<int,int>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define REPDIS(i,be,en,j) for(int i = (be); i<=(en); i+=j)
#define REPD(i,be,en) for(int i = (be); i>=(en); i--)
#define REP(i,be,en) for(int i = (be); i<=(en); i++)
#define endl "\n"
#define MP make_pair
// #define int ll
//-----------------------------------------------------------------------------------------------//
int readInt(){
char c;
do{ c = getchar(); }while(c!='-' && !isdigit(c));
bool neg = (c=='-');
int res = neg?0:c-'0';
while(isdigit(c=getchar())) res = (res<<3)+(res<<1)+(c-'0');
return neg?-res:res;
}
//------------------------------------------------------------------------------------------------//
const ll LINF = 1e18;
const int INF = 1e9;
const int LOG = 20;
const int MAXN = 1e3+3;
const int N = 1e2+3;
const int MOD = 1e9+7;
const int BASE = 1e5;
const ld EPS = 1e-9;
const ld PI = acos(-1);
const int OFFSET = 1e3;
const int dx[] = {-1,0,1,0};
const int dy[] = {0,-1,0,1};
//------------------------------------------------------------------------------------------------//
template<typename T1, typename T2> bool mini(T1 &a, T2 b){if(a>b){a=b;return true;}return false;}
template<typename T1, typename T2> bool maxi(T1 &a, T2 b){if(a<b){a=b;return true;}return false;}
template<typename T> T gcd(T a, T b) { while(b) { a %= b; swap(a,b); } return a; }
template<typename T> T lcm(T a, T b) { return a/gcd(a,b)*b; }
//------------------------------------------------------------------------------------------------//
/*
----------------------------------------------------------------
END OF TEMPLATE
----------------------------------------------------------------
Nguyen Ngoc Hung - nnhzzz
Training for VOI24 gold medal
----------------------------------------------------------------
*/
struct Node{
int w,u,v;
bool operator < (const Node &other) const {
return w>other.w;
}
};
int dis_wall[MAXN][MAXN],f[MAXN][MAXN];
pii nxt[MAXN][MAXN][4];
char c[MAXN][MAXN];
pii S,T;
int n,m;
void solve(){
cin >> n >> m;
REP(i,0,n+1) REP(j,0,m+1){
c[i][j] = '#';
f[i][j] = dis_wall[i][j] = INF;
}
queue<pii> q;
REP(i,1,n){
REP(j,1,m){
cin >> c[i][j];
if(c[i][j]=='S') S.fi = i,S.se = j;
if(c[i][j]=='C') T.fi = i,T.se = j;
}
}
REP(i,0,n+1) REP(j,0,m+1){
if(c[i][j]=='#'){
dis_wall[i][j] = 0;
q.push(MP(i,j));
}
}
REP(i,1,n){
REP(j,1,m){
if(c[i-1][j]=='#') nxt[i][j][2] = MP(i,j);
else nxt[i][j][2] = nxt[i-1][j][2];
if(c[i][j-1]=='#') nxt[i][j][3] = MP(i,j);
else nxt[i][j][3] = nxt[i][j-1][3];
}
}
REPD(i,n,1){
REPD(j,m,1){
if(c[i+1][j]=='#') nxt[i][j][0] = MP(i,j);
else nxt[i][j][0] = nxt[i+1][j][0];
if(c[i][j+1]=='#') nxt[i][j][1] = MP(i,j);
else nxt[i][j][1] = nxt[i][j+1][1];
}
}
while(SZ(q)!=0){
int x = q.front().fi,y = q.front().se; q.pop();
REP(i,0,3){
int nx = x+dx[i],ny = y+dy[i];
if(nx<0 || ny<0 || nx>n+1 || ny>m+1 || dis_wall[nx][ny]!=INF) continue;
dis_wall[nx][ny] = dis_wall[x][y]+1;
q.push(MP(nx,ny));
}
}
priority_queue<Node> heap;
heap.push({0,S.fi,S.se});
f[S.fi][S.se] = 0;
while(SZ(heap)!=0){
Node val = heap.top(); heap.pop();
int x = val.u,y = val.v,w = val.w;
if(f[x][y]!=w) continue;
REP(i,0,3){
int nx = x+dx[i],ny = y+dy[i];
if(c[nx][ny]!='#' && mini(f[nx][ny],f[x][y]+1)) heap.push({f[nx][ny],nx,ny});
nx = nxt[x][y][i].fi; ny = nxt[x][y][i].se;
if(mini(f[nx][ny],f[x][y]+dis_wall[x][y])) heap.push({f[nx][ny],nx,ny});
}
}
cout << f[T.fi][T.se];
}
__nnhzzz__{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#define task "test"
if(fopen(task".inp","r")){
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
#define task1 "nnhzzz"
if(fopen(task1".inp","r")){
freopen(task1".inp","r",stdin);
freopen(task1".out","w",stdout);
}
int test = 1;
while(test--){
solve();
}
cerr << "\nTime elapsed: " << 1000*clock()/CLOCKS_PER_SEC << "ms\n";
return 0;
}
/** /\_/\
* (= ._.)
* / >TL \>AC
**/
Compilation message (stderr)
portals.cpp: In function 'int main()':
portals.cpp:186:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
186 | freopen(task".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
portals.cpp:187:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
187 | freopen(task".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
portals.cpp:191:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
191 | freopen(task1".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
portals.cpp:192:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
192 | freopen(task1".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |