//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#define endl '\n'
int n,m;
int it[2001][2001];
vector<pair<pair<int,int>,int>> adj[2001][2001];
int dist[2001][2001];
pair<int,int> ba[2001][2001];
char ans[2001][2001];
vector<int> xx={0,0,-1,1};
vector<int> yy={1,-1,0,0};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>m;
pair<int,int> st;
pair<int,int> endd;
for(int i=0;i<n;i++){
string s;
cin>>s;
for(int j=0;j<m;j++){
ans[i][j]=s[j];
if(s[j]=='<'){
if(j>0){
adj[i][j].pb({{i,j-1},0});
}
}
else if(s[j]=='>'){
if(j+1<m){
adj[i][j].pb({{i,j+1},0});
}
}
else if(s[j]=='^'){
if(i>0){
adj[i][j].pb({{i-1,j},0});
}
}
else if(s[j]=='v'){
if(i+1<n){
adj[i][j].pb({{i+1,j},0});
}
}
else if(s[j]=='x'){
endd={i,j};
}
else if(s[j]=='.'){
}
else{
st={i,j};
}
}
}
/* for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
int cur=1;
if(i==st.a and j==st.b){
cur=0;
}
if(j>0){
adj[i][j].pb({{i,j-1},cur});
}
if(j+1<m){
adj[i][j].pb({{i,j+1},cur});
}
if(i>0){
adj[i][j].pb({{i-1,j},cur});
}
if(i+1<n){
adj[i][j].pb({{i+1,j},cur});
}
}
}*/
deque<pair<int,int>> ss;
ss.pb(st);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
dist[i][j]=n*m;
}
}
dist[st.a][st.b]=0;
while(ss.size()){
pair<int,int> no=ss.front();
ss.pop_front();
for(auto j:adj[no.a][no.b]){
if(dist[j.a.a][j.a.b]>dist[no.a][no.b]+j.b){
dist[j.a.a][j.a.b]=dist[no.a][no.b]+j.b;
ba[j.a.a][j.a.b]={no.a,no.b};
if(j.b==0){
ss.push_front(j.a);
}
else{
ss.pb(j.a);
}
}
}
for(int jj=0;jj<4;jj++){
pair<pair<int,int>,int> j={{no.a+xx[jj],no.b+yy[jj]},1};
if(j.a.a<0 or j.a.b<0 or j.a.a>=n or j.a.b>=m){
continue;
}
if(no.a==st.a and no.b==st.b){
j.b=0;
}
if(dist[j.a.a][j.a.b]>dist[no.a][no.b]+j.b){
dist[j.a.a][j.a.b]=dist[no.a][no.b]+j.b;
ba[j.a.a][j.a.b]={no.a,no.b};
if(j.b==0){
ss.push_front(j.a);
}
else{
ss.pb(j.a);
}
}
}
}
pair<int,int> cur;
cur=endd;
while(true){
pair<int,int> cur2;
cur2=cur;
cur=ba[cur.a][cur.b];
if(cur.a==st.a and cur.b==st.b){
break;
}
if(cur.a==endd.a and cur.b==endd.b){
continue;
}
if(cur.a+1==cur2.a){
ans[cur.a][cur.b]='v';
}
if(cur.a-1==cur2.a){
ans[cur.a][cur.b]='^';
}
if(cur.b-1==cur2.b){
ans[cur.a][cur.b]='<';
}
if(cur.b+1==cur2.b){
ans[cur.a][cur.b]='>';
}
}
cout<<dist[endd.a][endd.b]<<endl;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cout<<ans[i][j];
}
cout<<endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
64 ms |
94572 KB |
Output is correct |
| 2 |
Correct |
72 ms |
94444 KB |
Output is correct |
| 3 |
Correct |
70 ms |
94572 KB |
Output is correct |
| 4 |
Correct |
68 ms |
94572 KB |
Output is correct |
| 5 |
Correct |
72 ms |
94444 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
64 ms |
94572 KB |
Output is correct |
| 2 |
Correct |
72 ms |
94444 KB |
Output is correct |
| 3 |
Correct |
70 ms |
94572 KB |
Output is correct |
| 4 |
Correct |
68 ms |
94572 KB |
Output is correct |
| 5 |
Correct |
72 ms |
94444 KB |
Output is correct |
| 6 |
Correct |
174 ms |
119788 KB |
Output is correct |
| 7 |
Correct |
200 ms |
126836 KB |
Output is correct |
| 8 |
Correct |
348 ms |
153964 KB |
Output is correct |
| 9 |
Correct |
570 ms |
200856 KB |
Output is correct |
| 10 |
Correct |
838 ms |
223212 KB |
Output is correct |
| 11 |
Correct |
894 ms |
259232 KB |
Output is correct |
