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>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int , int> pii;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 1010;
const ll mod = 1e9+7;
#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}
int n , m;
char c[maxn][maxn];
int dist[maxn][maxn];
int nie[maxn][maxn];
struct tr{
int x , y , w;
friend bool operator < (tr a , tr b){
return a.w > b.w;
}
};
pii s , t;
vector < tr > adj[maxn][maxn];
priority_queue < tr > pq;
queue < pii > q;
bool mark[maxn][maxn];
void dijk(){
ms(dist , 63);
dist[s.first][s.second] = 0;
pq.push({s.first, s.second , 0});
while(pq.size()){
auto v = pq.top();
pq.pop();
if(mark[v.x][v.y])continue;
if(v.x == t.first and v.y == t.second)dokme(v.w);
mark[v.x][v.y] = 1;
for(tr u : adj[v.x][v.y])
if(dist[u.x][u.y] > v.w + u.w)
dist[u.x][u.y] = v.w + u.w , pq.push({u.x , u.y , v.w + u.w});
}
}
pii tmp[maxn][maxn];
int32_t main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin >> n >> m;
for(int i = 1 ; i <= n ; i ++){
cin >> (c[i]+1);
for(int j = 1 ; j <= m ; j ++)
if(c[i][j] == 'C')
t = {i , j};
else if(c[i][j] == 'S')
s = {i , j};
}
ms(nie , -1);
for(int i = 1 ; i <= n ; i ++)
for(int j = 1 ; j <= m ; j ++)
if(c[i][j] == '#')
nie[i][j] = 0 , q.push({i , j});
for(int i = 1 ; i <= m ; i ++)
nie[0][i] = 0 , q.push({0 , i}),
nie[n + 1][i] = 0 , q.push({n + 1 , i});
for(int i = 1 ; i <= n ; i ++)
nie[i][0] = 0 , q.push({i , 0}),
nie[i][m+1] = 0 , q.push({i , m+1});
while(q.size()){
pii v = q.front();
q.pop();
if(v.first > 1){
if(nie[v.first - 1][v.second] == -1)
nie[v.first - 1][v.second] = nie[v.first][v.second] + 1 ,
q.push({v.first - 1 , v.second});
}
if(v.first < n){
if(nie[v.first + 1][v.second] == -1)
nie[v.first + 1][v.second] = nie[v.first][v.second] + 1,
q.push({v.first + 1 , v.second});
}
if(v.second > 1){
if(nie[v.first][v.second - 1] == -1)
nie[v.first][v.second - 1] = nie[v.first][v.second] + 1,
q.push({v.first , v.second-1});
}
if(v.second < m){
if(nie[v.first][v.second + 1] == -1)
nie[v.first][v.second + 1] = nie[v.first][v.second] + 1,
q.push({v.first , v.second+1});
}
}
for(int i = 1 ; i <= n ; i ++)
for(int j = 1 ; j <= m ; j ++){
if(c[i][j] == '#')continue;
if(i > 1){
if(c[i-1][j] != '#')adj[i][j].pb({i-1 , j , 1});
}
if(i < n){
if(c[i+1][j] != '#')adj[i][j].pb({i+1 , j , 1});
}
if(j > 1){
if(c[i][j-1] != '#')adj[i][j].pb({i , j-1 , 1});
}
if(j < m){
if(c[i][j+1] != '#')adj[i][j].pb({i , j+1 , 1});
}
}
for(int i = 1 ; i <= n; i ++){
c[i][0] = '#';
for(int j = 1 ; j <= m ; j ++){
if(c[i][j] == '#')continue;
if(c[i][j-1] == '#')tmp[i][j] = {i , j};
else tmp[i][j] = tmp[i][j-1];
adj[i][j].pb({tmp[i][j].first , tmp[i][j].second , nie[i][j]});
}
}
for(int i = 1 ; i <= n; i ++){
c[i][m+1] = '#';
for(int j = m ; j >= 1; j --){
if(c[i][j] == '#')continue;
if(c[i][j+1] == '#')tmp[i][j] = {i , j};
else tmp[i][j] = tmp[i][j+1];
adj[i][j].pb({tmp[i][j].first , tmp[i][j].second , nie[i][j]});
}
}
for(int i = 1 ; i <= m; i ++){
c[0][i] = '#';
for(int j = 1 ; j <= n ; j ++){
if(c[j][i] == '#')continue;
if(c[j-1][i] == '#')tmp[j][i] = {j , i};
else tmp[j][i] = tmp[j-1][i];
adj[j][i].pb({tmp[j][i].first , tmp[j][i].second , nie[j][i]});
}
}
for(int i = 1 ; i <= m; i ++){
c[n+1][i] = '#';
for(int j = n ; j >= 1 ; j --){
if(c[j][i] == '#')continue;
if(c[j+1][i] == '#')tmp[j][i] = {j , i};
else tmp[j][i] = tmp[j+1][i];
adj[j][i].pb({tmp[j][i].first , tmp[j][i].second , nie[j][i]});
}
}
dijk();
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... |