| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 369437 |
2021-02-21T16:50:12 Z |
YJU |
Robots (APIO13_robots) |
C++14 |
|
97 ms |
163844 KB |
#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef long long 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<<60);
#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;
}
};
priority_queue<node,vector<node>,cmp> pq;
ll dp[10][10][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;
char grid[N][N];
bool invalid(ll x,ll y){
return !(0<x&&x<=R&&0<y&&y<=C&&grid[x][y]!='x');
}
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)REP1(j,C){
while((grid[i][j]=getchar())=='\n');
//cin>>grid[i][j];
}
//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++){
//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]);
}
}
//
dis[i][j][0][0]=dp[l][r][i][j];
if(dis[i][j][0][0]<INF){
pq.push(node(dis[i][j][0][0],i,j,0,0));
}
//
}
//moving robots ( O(N*N*log(N*N) ) )
while(SZ(pq)){
node nd=pq.top();pq.pop();
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){
//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.push(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(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(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(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(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(node(nd.Dis,nd.x,nd.y,0,nd.dir));
}
}
}
}
//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 |
Runtime error |
97 ms |
163844 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
97 ms |
163844 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
97 ms |
163844 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
97 ms |
163844 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
