#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[2500][2500][10],n,m,a[2500][2500];
pii father[2500][2500][10];
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;
int huong=1;
cout<<dp[t.fi][t.se][1]-1<<endl;
while (x!=s.fi || y!=s.se)
{
//cout<<x<<" "<<y<<" "<<huong<<endl;
a[x][y]=huong;
int new_huong=father[x][y][huong].fi;
int new_x=father[x][y][huong].se.fi;
int new_y=father[x][y][huong].se.se;
x=new_x;
y=new_y;
huong=new_huong;
}
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<super, vector <super>, greater<super> > p;
forw(i,1,n)
forw(j,1,m)
forw(k,1,4)
dp[i][j][k]=1e9;
forw(i,1,4)
{
dp[x][y][i]=0;
p.pu({0,{x,y,i}});
}
while (!p.empty())
{
int val=p.top().fi;
x=p.top().se[0];
y=p.top().se[1];
int huong=p.top().se[2];
p.pop();
if (val>dp[x][y][huong]) continue;
////////////////
int xx=x+tx[huong];
int yy=y+ty[huong];
if (!check(xx,yy)) continue;
forw(i,1,4)
if (a[xx][yy]!=i)
{
if (val+1<dp[xx][yy][i])
{
father[xx][yy][i]={huong,{x,y}};
dp[xx][yy][i]=val+1;
p.pu({val+1,{xx,yy,i}});
}
}
else
if (val<dp[xx][yy][i])
{
father[xx][yy][i]={huong,{x,y}};
dp[xx][yy][i]=val;
p.pu({val,{xx,yy,i}});
}
///////////////
}
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 |
460 KB |
Output is correct |
| 3 |
Correct |
1 ms |
588 KB |
Output is correct |
| 4 |
Correct |
1 ms |
588 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 |
460 KB |
Output is correct |
| 3 |
Correct |
1 ms |
588 KB |
Output is correct |
| 4 |
Correct |
1 ms |
588 KB |
Output is correct |
| 5 |
Correct |
0 ms |
332 KB |
Output is correct |
| 6 |
Correct |
874 ms |
146760 KB |
Output is correct |
| 7 |
Correct |
1412 ms |
182040 KB |
Output is correct |
| 8 |
Execution timed out |
2112 ms |
333692 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
