| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 934568 |
2024-02-27T15:23:27 Z |
8pete8 |
Robots (APIO13_robots) |
C++17 |
|
1500 ms |
89008 KB |
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<cassert>
#include<limits.h>
#include<cmath>
#include<set>
#include<numeric> //gcd(a,b)
#include<algorithm>
#include<bitset>
#include<stack>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define pppiiii pair<pii,pii>
#define ppii pair<int,pii>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
//#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
#define int long long
const int mod=1e9+7,mxn=505,lg=30,inf=1e18,minf=-1e18,Mxn=2e6,root=700;
void setIO(string name){
ios_base::sync_with_stdio(0); cin.tie(0);
freopen((name+".in").c_str(),"r",stdin);
freopen((name+".out").c_str(),"w",stdout);
}
pii pos[10];
char grid[mxn+10][mxn+10];
int n,h,w;
int dist[mxn+10][mxn+10][4];
vector<vector<int>>dp[10][10];
int u[4]={1,0,-1,0},r[4]={0,-1,0,1};
bool valid(int x,int y){
if(x<=0||x>h||y<=0||y>w)return false;
if(grid[x][y]=='x')return false;
return true;
}
struct node{
int x,y,stp,di;
bool operator<(const node o)const{return stp>o.stp;}
};
vector<vector<int>> play(int ind){//get min dist
int x=pos[ind].f,y=pos[ind].s;
vector<vector<int>>realdist(h+1,vector<int>(w+1,inf));
for(int i=1;i<=h;i++)for(int j=1;j<=w;j++)for(int k=0;k<4;k++)dist[i][j][k]=inf;
queue<node>q;
realdist[x][y]=0;
for(int i=0;i<4;i++)q.push({x,y,1,i});
while(!q.empty()){
auto [cx,cy,stp,di]=q.front();
q.pop();
if(dist[cx][cy][di]<=stp)continue;
dist[cx][cy][di]=stp;
if((grid[cx][cy]=='A'||grid[cx][cy]=='C')){
int add=1;
if(grid[cx][cy]=='A')add=-1;
di=(di+add+4)%4;
}
int nx=cx+u[di],ny=cy+r[di];
if(valid(nx,ny)){
if(dist[nx][ny][di]>stp)q.push({nx,ny,stp,di});
}
else{
realdist[cx][cy]=min(realdist[cx][cy],stp);
for(int k=0;k<4;k++)if(dist[cx][cy][k]>stp+1)q.push({cx,cy,stp+1,k});
}
}
return realdist;
}
void move(vector<vector<int>>&v){//move val
for(int i=1;i<=h;i++)for(int j=1;j<=w;j++)for(int k=0;k<4;k++)dist[i][j][k]=inf;
queue<node>q;
for(int i=1;i<=h;i++)for(int j=1;j<=w;j++){
if(v[i][j]==inf)continue;
for(int k=0;k<4;k++)q.push({i,j,v[i][j]+1,k});
}
while(!q.empty()){
auto [cx,cy,stp,di]=q.front();
q.pop();
if(dist[cx][cy][di]<=stp)continue;
dist[cx][cy][di]=stp;
if((grid[cx][cy]=='A'||grid[cx][cy]=='C')){
int add=1;
if(grid[cx][cy]=='A')add=-1;
di=(di+add+4)%4;
}
int nx=cx+u[di],ny=cy+r[di];
if(valid(nx,ny)){
if(dist[nx][ny][di]>stp)q.push({nx,ny,stp,di});
}
else{
v[cx][cy]=min(v[cx][cy],stp);
for(int k=0;k<4;k++)if(dist[cx][cy][k]>stp+1)q.push({cx,cy,stp+1,k});
}
}
}
int dp2[10][mxn+10][mxn+10];
int32_t main(){
fastio
cin>>n>>w>>h;
int ans=inf;
for(int i=1;i<=9;i++)for(int j=1;j<=9;j++)dp[i][j].resize(h+1,vector<int>(w+1,inf));
for(int i=1;i<=n;i++)for(int x=1;x<=h;x++)for(int y=1;y<=w;y++)dp2[i][x][y]=inf;
for(int i=1;i<=h;i++)for(int j=1;j<=w;j++){
cin>>grid[i][j];
if(grid[i][j]>='1'&&grid[i][j]<='9')pos[grid[i][j]-'0']={i,j};
}
for(int i=1;i<=n;i++)dp[i][i]=play(i);
for(int i=1;i<=n;i++)for(int j=i-1;j>=1;j--){
for(int x=1;x<=h;x++){
for(int y=1;y<=w;y++){
dp[i][j][x][y]=min(inf,dp[i][j+1][x][y]+dp[j][j][x][y]);
}
}
move(dp[i][j]);
}
//O(300*300*9*9+(300*300*lg))
//= 8,550,000*7
for(int x=1;x<=h;x++)for(int y=1;y<=w;y++){
for(int i=1;i<=n;i++){
for(int j=i;j>=1;j--)dp2[i][x][y]=min(dp2[i][x][y],dp[i][j][x][y]+dp2[j-1][x][y]);
}
}
for(int x=1;x<=h;x++)for(int y=1;y<=w;y++)ans=min(ans,dp2[n][x][y]);
cout<<((ans==inf)?-1:ans);
/*
for(int i=1;i<=2;i++){
//break;
}*/
//for(int i=1;i<=h;i++)for(int j=1;j<=w;j++)ans=min(ans,dp[i][j][n]);
/*
1 2 3
*/
}
Compilation message
robots.cpp: In function 'void setIO(std::string)':
robots.cpp:37:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
37 | freopen((name+".in").c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
robots.cpp:38:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
38 | freopen((name+".out").c_str(),"w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 5 |
Correct |
1 ms |
6492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 5 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 6 |
Correct |
1 ms |
6488 KB |
Output is correct |
| 7 |
Correct |
2 ms |
6488 KB |
Output is correct |
| 8 |
Correct |
1 ms |
6488 KB |
Output is correct |
| 9 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 10 |
Correct |
1 ms |
6492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 5 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 6 |
Correct |
1 ms |
6488 KB |
Output is correct |
| 7 |
Correct |
2 ms |
6488 KB |
Output is correct |
| 8 |
Correct |
1 ms |
6488 KB |
Output is correct |
| 9 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 10 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 11 |
Execution timed out |
1557 ms |
89008 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 5 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 6 |
Correct |
1 ms |
6488 KB |
Output is correct |
| 7 |
Correct |
2 ms |
6488 KB |
Output is correct |
| 8 |
Correct |
1 ms |
6488 KB |
Output is correct |
| 9 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 10 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 11 |
Execution timed out |
1557 ms |
89008 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
