| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 934815 |
2024-02-28T04:30:32 Z |
8pete8 |
Robots (APIO13_robots) |
C++17 |
|
3 ms |
12636 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*mxn+10],go[mxn+10][mxn+10][4];
vector<int> dp[10][10];
vector<int>adj[mxn*mxn+10];
int get(int x,int y){
return y+(x*w);
}
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 pos,stp;
bool operator<(const node o)const{return stp>o.stp;}
};
void move(vector<int>&v){
priority_queue<pii,vector<pii>,greater<pii>>pq;
for(int i=1;i<=v.size();i++)if(v[i]!=inf)pq.push({v[i],i});
while(!pq.empty()){
int cur=pq.top().s,cost=pq.top().f;
pq.pop();
if(cost>v[cur])continue;
for(auto i:adj[cur]){if(v[i]>v[cur]+1){
v[i]=v[cur]+1;
pq.push({v[i],i});
}
}
}
return;
}
int dp2[10][mxn*mxn+10];
int getnx(int x,int y,int di){
if(grid[x][y]=='A')di--;
else if(grid[x][y]=='C')di++;
di=(di+4)%4;
if(go[x][y][di])return go[x][y][di];
int nx=x+u[di],ny=y+r[di];
if(valid(nx,ny))return go[x][y][di]=getnx(nx,ny,di);
return go[x][y][di]=get(x,y);
}
//41->21->11
void print(int i,int j){
for(int x=1;x<=h;x++){
for(int y=1;y<=w;y++)cout<<((dp[i][j][get(x,y)]==inf)?-1:dp[i][j][get(x,y)])<<" ";
cout<<'\n';
}
cout<<'\n';
}
int32_t main(){
fastio
cin>>n>>w>>h;
int ans=inf;
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dp[i][j].resize((h+1)*(w+1),inf);
for(int i=1;i<=n;i++)for(int x=1;x<=h*w;x++)dp2[i][x]=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<=h;i++)for(int j=1;j<=w;j++)for(int k=0;k<4;k++)adj[get(i,j)].pb(getnx(i,j,k));
for(int i=1;i<=n;i++){
dp[i][i][get(pos[i].f,pos[i].s)]=0;
move(dp[i][i]);
}
for(int i=1;i<=n;i++)for(int j=i-1;j>=1;j--){
for(int x=1;x<=h*w;x++){
dp[i][j][x]=min(inf,dp[i][j+1][x]+dp[j][j][x]);
}
move(dp[i][j]);
}
for(int x=1;x<=h*w;x++){
for(int i=1;i<=n;i++){
for(int j=i;j>=1;j--)dp2[i][x]=min(dp2[i][x],dp[i][j][x]+dp2[j-1][x]);
}
}
for(int x=1;x<=h*w;x++)ans=min(ans,dp2[n][x]);
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 move(std::vector<long long int>&)':
robots.cpp:61:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for(int i=1;i<=v.size();i++)if(v[i]!=inf)pq.push({v[i],i});
| ~^~~~~~~~~~
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 |
Incorrect |
3 ms |
12636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
12636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
12636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
12636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
