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>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 2e3+5, M = N*N;
char grid[N][N], fromc[M];
vector<pair<pair<int,int>,char>> adj[M];
int from[M];
int n,m,dis[M], sx, sy, ex, ey;
void add_edge(int u, int v, int w, char c){
if(u==-1||v==-1) return;
adj[u].push_back({{v,w},c});
}
int encode(int i, int j){
if(i<0||j<0||i >= n || j >= m) return -1;
return i*N+j+1;
}
pair<int,int> decode(int num){
return {num/N, num%N-1};
}
signed main(){
fastio
cin >> n >> m;
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
cin >> grid[i][j];
if(grid[i][j]=='o') sx = i, sy = j;
if(grid[i][j]=='x') ex = i, ey = j;
}
}
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
int a = (grid[i][j]!='>'),b = (grid[i][j]!='^'),c = (grid[i][j]!='<'),d = (grid[i][j]!='v');
if(grid[i][j]=='o') a = b = c = d = 0;
add_edge(encode(i,j),encode(i,j+1),a,'>');
add_edge(encode(i,j),encode(i-1,j),b,'^');
add_edge(encode(i,j),encode(i,j-1),c,'<');
add_edge(encode(i,j),encode(i+1,j),d,'v');
}
}
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> pq;
fill(dis,dis+M,1e9+7);
dis[encode(sx,sy)] = 0;
pq.push({0,encode(sx,sy)});
while(!pq.empty()){
auto [ww,u] = pq.top(); pq.pop();
if(ww > dis[u]) continue;
for(auto [p,c] : adj[u]){
auto [v,w] = p;
if(dis[v] > dis[u]+w){
dis[v] = dis[u]+w;
from[v] = u;
fromc[v] = c;
pq.push({dis[v],v});
}
}
}
cout << dis[encode(ex,ey)] << "\n";
while(grid[ex][ey]!='o'){
char c = fromc[encode(ex,ey)];
auto p = decode(from[encode(ex,ey)]);
ex = p.first, ey = p.second;
if(ex==sx&&ey==sy) break;
grid[ex][ey] = c;
}
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
cout << grid[i][j];
}
cout << "\n";
}
}
Compilation message (stderr)
Main.cpp: In function 'int main()':
Main.cpp:52:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
52 | auto [ww,u] = pq.top(); pq.pop();
| ^
Main.cpp:54:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
54 | for(auto [p,c] : adj[u]){
| ^
Main.cpp:55:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
55 | auto [v,w] = p;
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |