| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 934834 |
2024-02-28T05:05:49 Z |
8pete8 |
Robots (APIO13_robots) |
C++17 |
|
57 ms |
163840 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=600,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-1)*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;}
};
int cnt=0;
stack<int>wtf[Mxn+10];
void move(vector<int>&v){
for(int i=1;i<=v.size();i++)if(v[i]<=h*w)wtf[v[i]].push(i);
for(int i=0;i<=h*w;i++){
while(!wtf[i].empty()){
int cur=wtf[i].top();
wtf[i].pop();
if(v[cur]<i)continue;
for(auto j:adj[cur])if(v[j]>i+1&&i+1<=h*w){
v[j]=i+1;
if(v[j]>Mxn)assert(0);
wtf[v[j]].push(j);
}
}
}
return;
}
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<=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 sz=2;sz<=n;sz++){
for(int l=1,r=sz;r<=n;l++,r++){
for(int x=1;x<=h*w;x++){
for(int mid=l;mid<r;mid++)dp[l][r][x]=min(dp[l][r][x],dp[l][mid][x]+dp[mid+1][r][x]);
}
move(dp[l][r]);
}
}
for(int x=1;x<=h*w;x++)ans=min(ans,dp[1][n][x]);
cout<<((ans==inf)?-1:ans);
}
Compilation message
robots.cpp: In function 'void move(std::vector<long long int>&)':
robots.cpp:62: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]
62 | for(int i=1;i<=v.size();i++)if(v[i]<=h*w)wtf[v[i]].push(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 |
Runtime error |
57 ms |
163840 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
57 ms |
163840 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
57 ms |
163840 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
57 ms |
163840 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
