| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 726072 |
2023-04-18T12:23:09 Z |
vjudge1 |
Robots (APIO13_robots) |
C++17 |
|
0 ms |
0 KB |
#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define lastbit(i) __builtin_ctz(i)
const int inf=1e9;
int v1[]={-1,0,1,0};
int v2[]={0,1,0,-1};
char a[509][509];
pii nxt[509][509][4];
int dp[9][9][509][509];
vector<pii>g[509][509];
int vis[9][9];
pii pos[9];
int n,r,c;
pii cal(int i,int j,int hr){
if (nxt[i][j][hr]!=pii(0,0))return nxt[i][j][hr];
//cout<<i<<" "<<j<<" "<<hr<<'\n';
int lt=hr;
if (a[i][j]=='A')hr=(hr-1+4)%4;
if (a[i][j]=='C')hr=(hr+1)%4;
nxt[i][j][lt]={-1,-1};
//cout<<i<<" "<<j<<" "<<hr<<" "<<lt<<'\n';
int newi=i+v1[hr],newj=j+v2[hr];
if (newi==0||newj==0||newi>r||newj>c||a[newi][newj]=='x')return nxt[i][j][lt]={i,j};
return nxt[i][j][lt]=cal(newi,newj,hr);
}
int visit[509][509];
struct ver{
int i,j,dis;
bool operator < (const ver &p)const {
return dis>p.dis;
}
};
void cal(int l1,int r1){
if (vis[l1][r1])return;
vis[l1][r1]=1;
if (l1==r1){
for1(i,1,r){
for1(j,1,c){
dp[l1][l1][i][j]=inf;
}
}
dp[l1][l1][pos[l1].fi][pos[l1].se]=0;
memset(visit,0,sizeof(visit));
visit[pos[l1].fi][pos[l1].se]=1;
queue<pii>t;
t.push(pos[l1]);
while (!t.empty()){
auto u=t.front();
t.pop();
for (auto v:g[u.fi][u.se]){
if (visit[v.fi][v.se])continue;
visit[v.fi][v.se]=1;
dp[l1][l1][v.fi][v.se]=dp[l1][l1][u.fi][u.se]+1;
t.push(v);
}
}
return;
}
for1(i,1,r){
for1(j,1,c){
dp[l1][r1][i][j]=inf;
}
}
for1(id,l1,r1-1){
cal(l1,id);
cal(id+1,r1);
for1(i,1,r){
for1(j,1,c){
dp[l1][r1][i][j]=min({dp[l1][r1][i][j],inf,dp[l1][id][i][j]+dp[id+1][r1][i][j]});
}
}
}
memset(visit,0,sizeof( visit));
vector<ver>vcl;
for1(i,1,r){
for1(j,1,c){
if (dp[l1][r1][i][j]>=inf)continue;
vcl.pb({i,j,dp[l1][r1][i][j]});
}
}
sort(all(vcl));
deque<ver>t;
while (sz(t)||sz(vcl)){
if (t.empty()){
t.pb(vcl.back());
vcl.pop_back();
}
else {
if (sz(vcl)){
if (vcl.back().dis<t.front().dis){
t.push_front(vcl.back());
vcl.pop_back();
}
}
}
auto u=t.front();
t.pop_front();
//cout<<u.i<<" "<<u.j<<" "<<u.dis<<'\n';
if (visit[u.i][u.j])continue;
dp[l1][r1][u.i][u.j]=u.dis;
visit[u.i][u.j]=1;
for (auto v:g[u.i][u.j]){
if (visit[v.fi][v.se])continue;
ver ttt={v.fi,v.se,u.dis+1};
//if (u.i==1&&u.j==7)cout<<u.dis+1<<'\n';
t.pb(ttt);
}
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
//freopen(".INP","r",stdin);
//freopen(".OUT","w",stdout);
cin>>n>>c>>r;
for1(i,1,r){
for1(j,1,c){
cin>>a[i][j];
if (a[i][j]!='.'&&a[i][j]!='x'&&a[i][j]!='A'&&a[i][j]!='C'){
pos[a[i][j]-'1']={i,j};
}
}
}
//cal(5,5,1);
for1(i,1,r){
for1(j,1,c){
if (a[i][j]!='x'){
for1(k,0,3){
cal(i,j,k);
if (nxt[i][j][k]!=pii(-1,-1)&&nxt[i][j][k]!=pii(i,j)){
g[i][j].pb(nxt[i][j][k]);
}
}
}
}
}
//cal(5,5,1);
cal(0,n-1);
int ans=inf;
for1(i,1,r){
for1(j,1,c){
ans=min(ans,dp[0][n-1][i][j]);
}
}
//cal(2,3);
//cout<<dp[2][3][1][1];
if (ans>=inf)cout<<-1;
else cout<<ans;
//cout<<dp[2][3][1][1];
//cout<<pos[2].fi<<" "<<pos[2].se;
//cout<<nxt[pos[2].fi][pos[2].se][1].fi<<" "<<nxt[pos[2].fi][pos[2].se][1].se;
}
Compilation message
robots.cpp: In function 'void cal(int, int)':
robots.cpp:57:12: error: reference to 'visit' is ambiguous
57 | memset(visit,0,sizeof(visit));
| ^~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:133,
from robots.cpp:1:
/usr/include/c++/10/variant:1700:5: note: candidates are: 'template<class _Visitor, class ... _Variants> constexpr decltype(auto) std::visit(_Visitor&&, _Variants&& ...)'
1700 | visit(_Visitor&& __visitor, _Variants&&... __variants)
| ^~~~~
robots.cpp:40:5: note: 'int visit [509][509]'
40 | int visit[509][509];
| ^~~~~
robots.cpp:57:27: error: reference to 'visit' is ambiguous
57 | memset(visit,0,sizeof(visit));
| ^~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:133,
from robots.cpp:1:
/usr/include/c++/10/variant:1700:5: note: candidates are: 'template<class _Visitor, class ... _Variants> constexpr decltype(auto) std::visit(_Visitor&&, _Variants&& ...)'
1700 | visit(_Visitor&& __visitor, _Variants&&... __variants)
| ^~~~~
robots.cpp:40:5: note: 'int visit [509][509]'
40 | int visit[509][509];
| ^~~~~
robots.cpp:58:5: error: reference to 'visit' is ambiguous
58 | visit[pos[l1].fi][pos[l1].se]=1;
| ^~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:133,
from robots.cpp:1:
/usr/include/c++/10/variant:1700:5: note: candidates are: 'template<class _Visitor, class ... _Variants> constexpr decltype(auto) std::visit(_Visitor&&, _Variants&& ...)'
1700 | visit(_Visitor&& __visitor, _Variants&&... __variants)
| ^~~~~
robots.cpp:40:5: note: 'int visit [509][509]'
40 | int visit[509][509];
| ^~~~~
robots.cpp:65:17: error: reference to 'visit' is ambiguous
65 | if (visit[v.fi][v.se])continue;
| ^~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:133,
from robots.cpp:1:
/usr/include/c++/10/variant:1700:5: note: candidates are: 'template<class _Visitor, class ... _Variants> constexpr decltype(auto) std::visit(_Visitor&&, _Variants&& ...)'
1700 | visit(_Visitor&& __visitor, _Variants&&... __variants)
| ^~~~~
robots.cpp:40:5: note: 'int visit [509][509]'
40 | int visit[509][509];
| ^~~~~
robots.cpp:66:13: error: reference to 'visit' is ambiguous
66 | visit[v.fi][v.se]=1;
| ^~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:133,
from robots.cpp:1:
/usr/include/c++/10/variant:1700:5: note: candidates are: 'template<class _Visitor, class ... _Variants> constexpr decltype(auto) std::visit(_Visitor&&, _Variants&& ...)'
1700 | visit(_Visitor&& __visitor, _Variants&&... __variants)
| ^~~~~
robots.cpp:40:5: note: 'int visit [509][509]'
40 | int visit[509][509];
| ^~~~~
robots.cpp:87:8: error: reference to 'visit' is ambiguous
87 | memset(visit,0,sizeof( visit));
| ^~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:133,
from robots.cpp:1:
/usr/include/c++/10/variant:1700:5: note: candidates are: 'template<class _Visitor, class ... _Variants> constexpr decltype(auto) std::visit(_Visitor&&, _Variants&& ...)'
1700 | visit(_Visitor&& __visitor, _Variants&&... __variants)
| ^~~~~
robots.cpp:40:5: note: 'int visit [509][509]'
40 | int visit[509][509];
| ^~~~~
robots.cpp:87:24: error: reference to 'visit' is ambiguous
87 | memset(visit,0,sizeof( visit));
| ^~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:133,
from robots.cpp:1:
/usr/include/c++/10/variant:1700:5: note: candidates are: 'template<class _Visitor, class ... _Variants> constexpr decltype(auto) std::visit(_Visitor&&, _Variants&& ...)'
1700 | visit(_Visitor&& __visitor, _Variants&&... __variants)
| ^~~~~
robots.cpp:40:5: note: 'int visit [509][509]'
40 | int visit[509][509];
| ^~~~~
robots.cpp:113:9: error: reference to 'visit' is ambiguous
113 | if (visit[u.i][u.j])continue;
| ^~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:133,
from robots.cpp:1:
/usr/include/c++/10/variant:1700:5: note: candidates are: 'template<class _Visitor, class ... _Variants> constexpr decltype(auto) std::visit(_Visitor&&, _Variants&& ...)'
1700 | visit(_Visitor&& __visitor, _Variants&&... __variants)
| ^~~~~
robots.cpp:40:5: note: 'int visit [509][509]'
40 | int visit[509][509];
| ^~~~~
robots.cpp:115:5: error: reference to 'visit' is ambiguous
115 | visit[u.i][u.j]=1;
| ^~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:133,
from robots.cpp:1:
/usr/include/c++/10/variant:1700:5: note: candidates are: 'template<class _Visitor, class ... _Variants> constexpr decltype(auto) std::visit(_Visitor&&, _Variants&& ...)'
1700 | visit(_Visitor&& __visitor, _Variants&&... __variants)
| ^~~~~
robots.cpp:40:5: note: 'int visit [509][509]'
40 | int visit[509][509];
| ^~~~~
robots.cpp:117:13: error: reference to 'visit' is ambiguous
117 | if (visit[v.fi][v.se])continue;
| ^~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:133,
from robots.cpp:1:
/usr/include/c++/10/variant:1700:5: note: candidates are: 'template<class _Visitor, class ... _Variants> constexpr decltype(auto) std::visit(_Visitor&&, _Variants&& ...)'
1700 | visit(_Visitor&& __visitor, _Variants&&... __variants)
| ^~~~~
robots.cpp:40:5: note: 'int visit [509][509]'
40 | int visit[509][509];
| ^~~~~
