이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 add if (!A[x][y]) {g[id[i][j]].pb({id[x][y], w});}
const ll N = 1000 + 3;
const ll LOG = 17;
const ll INF = 1e9 + 5;
const ll MOD = 1e9 + 7;
int n, m;
string s;
bool A[N][N];
int id[N][N], ind = 1;
vector < pair <int, int> > g[N * N];
pair <int, int> st, en;
int le[N][N], ri[N][N];
int up[N][N], dw[N][N];
inline void pre(){
for (int i = 0; i <= n + 1; i ++){
for (int j = 0; j <= m + 1; j ++){
if (A[i][j]){
le[i][j] = j;
up[i][j] = i;
}
else {
le[i][j] = le[i][j - 1];
up[i][j] = up[i - 1][j];
}
}
}
for (int i = n + 1; i >= 0; i --){
for (int j = m + 1; j >= 0; j --){
if (A[i][j]){
ri[i][j] = j;
dw[i][j] = i;
}
else {
ri[i][j] = ri[i][j + 1];
dw[i][j] = dw[i + 1][j];
}
}
}
return;
}
int dis[N * N];
inline void add_edges(){
for (int i = 1; i <= n; i ++){
for (int j = 1; j <= m; j ++){
if (A[i][j]) continue;
int x, y;
int w = min({j - le[i][j], ri[i][j] - j, i - up[i][j], dw[i][j] - i});
x = i, y = le[i][j] + 1; add
x = i, y = ri[i][j] - 1; add
x = up[i][j] + 1, y = j; add
x = dw[i][j] - 1, y = j; add
w = 1;
x = i, y = j - 1; add
x = i, y = j + 1; add
x = i - 1, y = j; add
x = i + 1, y = j; add
}
}
return;
}
bool mark[N * N];
priority_queue < pair <int, 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;
}
}
dis[id[st.F][st.S]] = 0;
pq.push({0, id[st.F][st.S]});
while (pq.size()){
int v = pq.top().S;
pq.pop();
if (mark[v]) continue;
mark[v] = 1;
for (auto it : g[v]){
int w = it.S;
int 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 >> s; s = ' ' + s;
if (s[j] == 'S'){
st = {i, j};
}
else if (s[j] == 'C'){
en = {i, j};
}
A[i][j] = (s[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] = ind;
ind ++;
}
}
pre();
add_edges();
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... |