This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define ll long long
#define F first
#define S second
#define pb push_back
#define md ((b + e) >> 1)
const ll N = 1000 + 3;
const ll LOG = 17;
const ll INF = 1e9 + 5;
const ll MOD = 1e9 + 7;
short n, m;
char mat[N][N];
pair <short, short> L[N][N], R[N][N];
pair <short, short> U[N][N], D[N][N];
pair <int, int> dir[4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
vector <int> g[N * N];
vector < pair < int, int > > adj[N * N];
pair <short, short> st, en;
bool A[N][N];
int id[N][N], ID = 1;
inline bool in_sq(short x, short y){
return ((0 <= x) && (x <= n + 1) && (0 <= y) && (y <= m + 1));
}
inline bool valid(short x, short y){
return (in_sq(x, y) && !A[x][y]);
}
inline void add_edges(){
for (short i = 0; i <= n + 1; i ++){
for (short j = 0; j <= m + 1; j ++){
for (short d = 0; d < 4; d ++){
short x = i + dir[d].F;
short y = j + dir[d].S;
if (valid(x, y)){
g[id[i][j]].pb(id[x][y]);
}
}
}
}
return;
}
int dis[N * N];
queue <int> q;
inline void bfs(){
for (short i = 0; i <= n + 1; i ++){
for (short j = 0; j <= m + 1; j ++){
dis[id[i][j]] = INF;
}
}
for (short i = 0; i <= n + 1; i ++){
for (short j = 0; j <= m + 1; j ++){
if (A[i][j]){
dis[id[i][j]] = 0;
q.push(id[i][j]);
}
}
}
while (q.size()){
int v = q.front();
q.pop();
for (auto u : g[v]){
if (dis[v] + 1 < dis[u]){
dis[u] = dis[v] + 1;
q.push(u);
}
}
}
return;
}
inline void pre(){
for (short i = 0; i <= n + 1; i ++){
for (short j = 0; j <= m + 1; j ++){
if (A[i][j]){
L[i][j] = {i, j};
U[i][j] = {i, j};
}
else {
L[i][j] = L[i][j - 1];
U[i][j] = U[i - 1][j];
}
}
}
for (short i = n + 1; i >= 0; i --){
for (short j = m + 1; j >= 0; j --){
if (A[i][j]){
R[i][j] = {i, j};
D[i][j] = {i, j};
}
else {
R[i][j] = R[i][j + 1];
D[i][j] = D[i + 1][j];
}
}
}
return;
}
inline void add_edges2(){
for (short i = 0; i <= n + 1; i ++){
for (short j = 0; j <= m + 1; j ++){
if (!valid(i, j)) continue;
if (valid(i + 1, j)){
short x = D[i + 1][j].F - 1;
short y = D[i + 1][j].S;
if (!valid(x, y)) continue;
adj[id[i][j]].pb({id[x][y], dis[id[i][j]]});
}
if (valid(i, j + 1)){
short x = R[i][j + 1].F;
short y = R[i][j + 1].S - 1;
if (!valid(x, y)) continue;
adj[id[i][j]].pb({id[x][y], dis[id[i][j]]});
}
if (valid(i - 1, j)){
short x = U[i - 1][j].F + 1;
short y = U[i - 1][j].S;
if (!valid(x, y)) continue;
adj[id[i][j]].pb({id[x][y], dis[id[i][j]]});
}
if (valid(i, j - 1)){
short x = L[i][j - 1].F;
short y = L[i][j - 1].S + 1;
if (!valid(x, y)) continue;
adj[id[i][j]].pb({id[x][y], dis[id[i][j]]});
}
for (short d = 0; d < 4; d ++){
short x = i + dir[d].F;
short y = j + dir[d].S;
if (valid(x, y)){
adj[id[i][j]].pb({id[x][y], 1});
}
}
}
}
return;
}
bool mark[N * N];
priority_queue < pair < ll, int > > pq;
inline void dij(){
for (int i = 0; i <= n + 1; i ++){
for (int j = 0; j <= m + 1; j ++){
dis[id[i][j]] = INF;
}
}
pq.push({0, id[st.F][st.S]});
dis[id[st.F][st.S]] = 0;
while (pq.size()){
auto v = pq.top().S;
pq.pop();
if (mark[v]) continue;
mark[v] = 1;
if (v == id[en.F][en.S]) break;
for (auto it : adj[v]){
ll w = it.S;
auto u = it.F;
if (dis[v] + w < dis[u]){
dis[u] = dis[v] + w;
pq.push({-dis[u], u});
}
}
}
cout << dis[id[en.F][en.S]] << '\n';
return;
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i ++){
for (int j = 1; j <= m; j ++){
cin >> mat[i][j];
if (mat[i][j] == 'S'){
st = {i, j};
mat[i][j] = '.';
}
if (mat[i][j] == 'C'){
en = {i, j};
mat[i][j] = '.';
}
A[i][j] = (mat[i][j] == '#');
}
}
for (int i = 0; i <= n + 1; i ++){
A[i][0] = A[i][m + 1] = 1;
}
for (int j = 0; j <= m + 1; j ++){
A[0][j] = A[n + 1][j] = 1;
}
for (int i = 0; i <= n +1 ; i ++){
for (int j = 0; j <= m + 1; j ++){
id[i][j] = ID; ID ++;
}
}
add_edges();
bfs();
pre();
add_edges2();
dij();
return 0;
}
# | 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... |