| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 369446 |
2021-02-21T17:07:17 Z |
YJU |
Robots (APIO13_robots) |
C++14 |
|
1500 ms |
105772 KB |
#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef int ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=5e2+5;
const ld pi=acos(-1);
const ll INF=(1LL<<29);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()
struct node{
ll Dis,x,y,ty,dir;
node(ll _a,ll _b,ll _c,ll _d,ll _e):Dis(_a),x(_b),y(_c),ty(_d),dir(_e){};
//state :at (x,y) ty(turn yet?0:1) dir(direction)
// 3
// |
//4-0-2
// |
// 1
void out(){
cout<<"Dis("<<Dis<<"),x("<<x<<"),y("<<y<<"),ty("<<ty<<"),dir("<<dir<<")\n";
}
};
struct cmp{
bool operator()(node A,node B){
return A.Dis>B.Dis;
}
};
deque<node> pq;
//priority_queue<node,vector<node>,cmp> pq;
ll dp[11][11][N][N],dis[N][N][2][5];
//dp[l][r][x][y] represents minimum times of operation to make robot[l,r] stay at grid[x][y]
ll dx[5]={0,1,0,-1,0},dy[5]={0,0,1,0,-1};
ll n,R,C;
string grid[N];
bool invalid(ll x,ll y){
return !(0<x&&x<=R&&0<y&&y<=C&&grid[x][y]!='x');
}
void AAA(ll l,ll r){
while(SZ(pq)){
node nd=pq.front();pq.pop_front();
if(nd.Dis!=dis[nd.x][nd.y][nd.ty][nd.dir])continue;
//nd.out();
if(nd.ty==0){
//have turned
if(nd.dir==0){
dp[l][r][nd.x][nd.y]=min(dp[l][r][nd.x][nd.y],nd.Dis);
//stand at (nd.x,nd.y)
REP1(dir,4){
//push to dir (cost = 1)
if(dis[nd.x][nd.y][1][dir]>nd.Dis+1){
dis[nd.x][nd.y][1][dir]=nd.Dis+1;
pq.pb(node(nd.Dis+1,nd.x,nd.y,1,dir));
}
}
}else{
//moving on or stop (cost = 0)
if(invalid(nd.x+dx[nd.dir],nd.y+dy[nd.dir])){
if(dis[nd.x][nd.y][0][0]>nd.Dis){
dis[nd.x][nd.y][0][0]=nd.Dis;
pq.push_front(node(nd.Dis,nd.x,nd.y,0,0));
}
}else{
ll nx=nd.x+dx[nd.dir],ny=nd.y+dy[nd.dir];
if(dis[nx][ny][1][nd.dir]>nd.Dis){
dis[nx][ny][1][nd.dir]=nd.Dis;
pq.push_front(node(nd.Dis,nx,ny,1,nd.dir));
}
}
}
}else if(nd.ty==1){
if(nd.dir==0)continue;
if(grid[nd.x][nd.y]=='A'){
ll ndir=(nd.dir+1==5?1:nd.dir+1);
if(dis[nd.x][nd.y][0][ndir]>nd.Dis){
dis[nd.x][nd.y][0][ndir]=nd.Dis;
pq.push_front(node(nd.Dis,nd.x,nd.y,0,ndir));
}
}else if(grid[nd.x][nd.y]=='C'){
ll ndir=(nd.dir-1==0?4:nd.dir-1);
if(dis[nd.x][nd.y][0][ndir]>nd.Dis){
dis[nd.x][nd.y][0][ndir]=nd.Dis;
pq.push_front(node(nd.Dis,nd.x,nd.y,0,ndir));
}
}else{
if(dis[nd.x][nd.y][0][nd.dir]>nd.Dis){
dis[nd.x][nd.y][0][nd.dir]=nd.Dis;
pq.push_front(node(nd.Dis,nd.x,nd.y,0,nd.dir));
}
}
}
}
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
//prepare
REP(ii,10)REP(jj,10)REP(i,N)REP(j,N)dp[ii][jj][i][j]=INF;
//prepare end
//input
cin>>n>>C>>R;
REP1(i,R)cin>>grid[i],grid[i]="x"+grid[i];
//input end
//len = r-l+1 for robot[l,r]
for(int len=1;len<=n;len++){
for(int l=1,r=l+len-1;l+len-1<=n;l++,r++){
vector<node> lis;
//merging robots to robot[l,r]
REP1(i,R)REP1(j,C){
REP(ty,2)REP(dir,5)dis[i][j][ty][dir]=INF;
if(len==1){
dp[l][r][i][j]=(grid[i][j]-'0'==l?0:INF);
}else{
for(int cut=l;cut+1<=r;cut++){
dp[l][r][i][j]=min(dp[l][r][i][j],dp[l][cut][i][j]+dp[cut+1][r][i][j]);
}
}
//
if(dp[l][r][i][j]<INF){
lis.pb(node(dp[l][r][i][j],i,j,0,0));
}
//
}
sort(lis.begin(),lis.end(),[](node A,node B){
return A.Dis<B.Dis;
});
//moving robots ( O(N*N*log(N*N) ) )
for(node i:lis){
if(dis[i.x][i.y][0][0]>i.Dis){
dis[i.x][i.y][0][0]=i.Dis;
pq.pb(i);
AAA(l,r);
}
}
//update after moving
//cout<<"robot["<<l<<","<<r<<"]\n";
/*REP1(i,R)REP1(j,C){
dp[l][r][i][j]=min(dp[l][r][i][j],dis[i][j][0][0]);
//cout<<setw(2)<<(dp[l][r][i][j]==INF?-1:dp[l][r][i][j])<<(j==C?"\n":" ");
}*/
}
}
ll ans=INF;
REP1(i,R)REP1(j,C){
ans=min(ans,dp[1][n][i][j]);
}
cout<<(ans==INF?-1:ans)<<"\n";
return 0;
}
/*
4 10 5
1.........
AA...x4...
..A..x....
2....x....
..C.3.A...
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
100204 KB |
Output is correct |
| 2 |
Correct |
56 ms |
100204 KB |
Output is correct |
| 3 |
Correct |
56 ms |
100204 KB |
Output is correct |
| 4 |
Correct |
56 ms |
100332 KB |
Output is correct |
| 5 |
Correct |
55 ms |
100332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
100204 KB |
Output is correct |
| 2 |
Correct |
56 ms |
100204 KB |
Output is correct |
| 3 |
Correct |
56 ms |
100204 KB |
Output is correct |
| 4 |
Correct |
56 ms |
100332 KB |
Output is correct |
| 5 |
Correct |
55 ms |
100332 KB |
Output is correct |
| 6 |
Correct |
56 ms |
100204 KB |
Output is correct |
| 7 |
Correct |
56 ms |
100204 KB |
Output is correct |
| 8 |
Correct |
55 ms |
100204 KB |
Output is correct |
| 9 |
Correct |
57 ms |
100204 KB |
Output is correct |
| 10 |
Correct |
55 ms |
100332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
100204 KB |
Output is correct |
| 2 |
Correct |
56 ms |
100204 KB |
Output is correct |
| 3 |
Correct |
56 ms |
100204 KB |
Output is correct |
| 4 |
Correct |
56 ms |
100332 KB |
Output is correct |
| 5 |
Correct |
55 ms |
100332 KB |
Output is correct |
| 6 |
Correct |
56 ms |
100204 KB |
Output is correct |
| 7 |
Correct |
56 ms |
100204 KB |
Output is correct |
| 8 |
Correct |
55 ms |
100204 KB |
Output is correct |
| 9 |
Correct |
57 ms |
100204 KB |
Output is correct |
| 10 |
Correct |
55 ms |
100332 KB |
Output is correct |
| 11 |
Execution timed out |
1592 ms |
105772 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
100204 KB |
Output is correct |
| 2 |
Correct |
56 ms |
100204 KB |
Output is correct |
| 3 |
Correct |
56 ms |
100204 KB |
Output is correct |
| 4 |
Correct |
56 ms |
100332 KB |
Output is correct |
| 5 |
Correct |
55 ms |
100332 KB |
Output is correct |
| 6 |
Correct |
56 ms |
100204 KB |
Output is correct |
| 7 |
Correct |
56 ms |
100204 KB |
Output is correct |
| 8 |
Correct |
55 ms |
100204 KB |
Output is correct |
| 9 |
Correct |
57 ms |
100204 KB |
Output is correct |
| 10 |
Correct |
55 ms |
100332 KB |
Output is correct |
| 11 |
Execution timed out |
1592 ms |
105772 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
