#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pi;
typedef pair<ll, pair<ll, ll> > pii;
typedef vector <ll> vi;
typedef pair < ll, vector <ll> > super;
#define forw(i,a,b) for (ll i=a;i<=(b);i++)
#define forb(i,a,b) for (ll i=a;i>=(b);i--)
#define fast {ios::sync_with_stdio(false); cin.tie(0); }
#define fi first
#define se second
#define pu push
#define puf push_front
#define pb push_back
#define pof pop_front
#define pob pop_back
#define fr front
#define all(a) a.begin(),a.end()
const ll oo=1e18;
const ll mod=1e9+7;
const int base=31;
const int tx[5]={0,-1,0,1,0};
const int ty[5]={0,0,1,0,-1};
const ll maxN=2e5+5;
int dp[2005][2005],n,m,a[2005][2005];
pi father[2005][2005];
pi s,t;
bool check(int x, int y)
{
if (1<=x && x<=n)
if (1<=y && y<=m) return true;
return false;
}
void print()
{
int x=t.fi;
int y=t.se;
cout<<dp[t.fi][t.se]-1<<endl;
while (x!=s.fi || y!=s.se)
{
forw(huong,1,4)
if (father[x][y].fi+tx[huong]==x && father[x][y].se+ty[huong]==y)
{
a[father[x][y].fi][father[x][y].se]=huong;
break;
}
int new_x=father[x][y].fi;
int new_y=father[x][y].se;
x=new_x;
y=new_y;
}
forw(i,1,n)
{
forw(j,1,m)
{
if (i==t.fi && j==t.se) cout<<'x';
else if (i==s.fi && j==s.se) cout<<'o';
else if (a[i][j]==0) cout<<'.';
else if (a[i][j]==1) cout<<'^';
else if (a[i][j]==2) cout<<'>';
else if (a[i][j]==3) cout<<'v';
else cout<<'<';
}
cout<<endl;
}
return;
}
void dijk(int x, int y)
{
priority_queue<pii, vector <pii>, greater<pii> > p;
forw(i,1,n)
forw(j,1,m)
forw(k,1,4)
dp[i][j]=1e9;
dp[x][y]=0;
p.pu({0,{x,y}});
while (!p.empty())
{
int val=p.top().fi;
x=p.top().se.fi;
y=p.top().se.se;
p.pop();
if (val>dp[x][y]) continue;
////////////////
forw(huong,1,4)
{
int xx=x+tx[huong];
int yy=y+ty[huong];
int dodai=val+(huong!=a[x][y]);
if (check(xx,yy) && dodai<dp[xx][yy])
{
father[xx][yy]={x,y};
dp[xx][yy]=dodai;
p.pu({dodai,{xx,yy}});
}
}
///////////////
}
return;
}
void solve()
{
cin>>n>>m;
s={0,0};
t={0,0};
forw(i,1,n)
forw(j,1,m)
{
char c;
cin>>c;
if (c=='^') a[i][j]=1;
else
if (c=='>') a[i][j]=2;
else
if (c=='v') a[i][j]=3;
else
if (c=='<') a[i][j]=4;
if (c=='o') s={i,j};
if (c=='x') t={i,j};
}
dijk(s.fi,s.se);
print();
}
int main()
{
fast;
//freopen("test.inp","r",stdin);
//freopen("test.out","w",stdout);
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
460 KB |
Output is correct |
| 4 |
Correct |
1 ms |
460 KB |
Output is correct |
| 5 |
Correct |
0 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
460 KB |
Output is correct |
| 4 |
Correct |
1 ms |
460 KB |
Output is correct |
| 5 |
Correct |
0 ms |
332 KB |
Output is correct |
| 6 |
Correct |
160 ms |
19956 KB |
Output is correct |
| 7 |
Correct |
182 ms |
26120 KB |
Output is correct |
| 8 |
Correct |
388 ms |
43276 KB |
Output is correct |
| 9 |
Correct |
863 ms |
70816 KB |
Output is correct |
| 10 |
Correct |
958 ms |
88836 KB |
Output is correct |
| 11 |
Correct |
1367 ms |
112920 KB |
Output is correct |
