제출 #385586

#제출 시각아이디문제언어결과실행 시간메모리
385586ogibogi2004로봇 (APIO13_robots)C++14
100 / 100
461 ms155628 KiB
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize ("Ofast") #pragma GCC target ("fma,avx,avx2") #define ends dfdsfdsf const int INF=1e8; pair<pair<int,int>,char> nxt[502][502][4]; vector<pair<pair<int,int>,char> >g[502][502][4]; pair<int,int>g1[502][502][4]; int deg[502][502]; char table[502][502]; int r,n,m; vector<pair<pair<int,int>,char> >ends; pair<pair<int,int>,char> actual_nxt[502][502][4]; bool not_valid(pair<int,int> p) { int x=p.first,y=p.second; if(x<1||y<1||x>n||y>m)return 1; return table[x][y]=='x'; } int dp[45][502][502]; pair<int,int> where[10]; int number[10][10]; void pre() { int cnt=0; for(int i=1;i<=9;++i) { for(int j=i;j<=9;++j) { number[i][j]=++cnt; } } } vector<pair<short,short> >pq[1000000]; int main() { pre(); ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>r>>m>>n; for(int i=1;i<=n;++i) { for(int j=1;j<=m;++j) { cin>>table[i][j]; if(isdigit(table[i][j])) { where[table[i][j]-'0']={i,j}; } } } for(int i=1;i<=n;++i) { for(int j=1;j<=m;++j) { if(table[i][j]=='x')continue; if(table[i][j]=='A') { nxt[i][j][0]={{i,j-1},3}; nxt[i][j][1]={{i-1,j},0}; nxt[i][j][2]={{i,j+1},1}; nxt[i][j][3]={{i+1,j},2}; } else if(table[i][j]=='C') { nxt[i][j][0]={{i,j+1},1}; nxt[i][j][1]={{i+1,j},2}; nxt[i][j][2]={{i,j-1},3}; nxt[i][j][3]={{i-1,j},0}; } else { nxt[i][j][0]={{i-1,j},0}; nxt[i][j][1]={{i,j+1},1}; nxt[i][j][2]={{i+1,j},2}; nxt[i][j][3]={{i,j-1},3}; } for(int l=0;l<4;++l) { if(not_valid(nxt[i][j][l].first)) { ends.push_back({{i,j},l}); } g[nxt[i][j][l].first.first][nxt[i][j][l].first.second][nxt[i][j][l].second].push_back({{i,j},l}); } } } queue<pair<pair<int,int>,char> >qq; for(auto xd:ends) { qq.push(xd); actual_nxt[xd.first.first][xd.first.second][xd.second]=xd; } while(!qq.empty()) { auto u=qq.front(); qq.pop(); for(auto xd:g[u.first.first][u.first.second][u.second]) { actual_nxt[xd.first.first][xd.first.second][xd.second]=actual_nxt[u.first.first][u.first.second][u.second]; qq.push(xd); } } for(int i=1;i<=n;++i) { for(int j=1;j<=m;++j) { for(int l=0;l<4;++l) { int x,y,z; x=actual_nxt[i][j][l].first.first; y=actual_nxt[i][j][l].first.second; z=actual_nxt[i][j][l].second; if(x==i&&y==j&&z==l)continue; g1[i][j][deg[i][j]++]={x,y}; } } } for(int r1=1;r1<=r;++r1) { for(int r2=1;r2<=r;++r2) { for(int i1=1;i1<=n;++i1) { for(int i2=1;i2<=m;++i2) { dp[number[r1][r2]][i1][i2]=INF; } } } } queue<pair<int,int> >q; for(int i=1;i<=r;++i) { int x,y; x=where[i].first; y=where[i].second; q.push({x,y}); dp[number[i][i]][x][y]=0; while(!q.empty()) { tie(x,y)=q.front(); q.pop(); for(int jj=0;jj<deg[x][y];jj++) { pair<int,int> xd=g1[x][y][jj]; if(dp[number[i][i]][xd.first][xd.second]>dp[number[i][i]][x][y]+1) { dp[number[i][i]][xd.first][xd.second]=dp[number[i][i]][x][y]+1; q.push(xd); } } } } vector<int>dps; for(int len=2;len<=r;++len) { for(int r1=1;r1+len-1<=r;++r1) { int r2=r1+len-1; int cc=number[r1][r2]; for(int mid=r1;mid<r2;++mid) { for(int i=1;i<=n;++i) { for(int j=1;j<=m;++j) { dp[cc][i][j]=min(dp[cc][i][j],dp[number[r1][mid]][i][j]+dp[number[mid+1][r2]][i][j]); } } } int mindp=INF; for(int i=1;i<=n;++i) { for(int j=1;j<=m;++j) { mindp=min(mindp,dp[cc][i][j]); if(dp[cc][i][j]<INF) { pq[dp[cc][i][j]].push_back({i,j}); dps.push_back(dp[cc][i][j]); } } } if(mindp>=INF)continue; for(int j=0;j<pq[mindp].size();j++)q.push({pq[mindp][j].first,pq[mindp][j].second}); pq[mindp].clear(); while(!q.empty()) { int x,y; tie(x,y)=q.front(); q.pop(); for(int jj=0;jj<deg[x][y];jj++) { pair<int,int> xd=g1[x][y][jj]; if(dp[cc][x][y]+1<dp[cc][xd.first][xd.second]) { dp[cc][xd.first][xd.second]=dp[cc][x][y]+1; q.push(xd); } } if(dp[cc][x][y]+1<INF&&pq[dp[cc][x][y]+1].size()!=0) { for(int ii=0;ii<pq[dp[cc][x][y]+1].size();ii++) { pair<int,int> xd=pq[dp[cc][x][y]+1][ii]; if(dp[cc][xd.first][xd.second]!=dp[cc][x][y]+1)continue; q.push(xd); } pq[dp[cc][x][y]+1].clear(); } } for(int j=0;j<dps.size();j++)pq[dps[j]].clear(); dps.clear(); } } /*for(int i1=1;i1<=r;i1++) { for(int i2=i1;i2<=r;i2++) { cout<<i1<<"-"<<i2<<endl; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(dp[i1][i2][i][j]<INF)cout<<dp[i1][i2][i][j]; else cout<<"x"; } cout<<endl; } } }*/ int ans=INF; for(int i=1;i<=n;++i) { for(int j=1;j<=m;++j) { ans=min(ans,dp[number[1][r]][i][j]); } } if(ans==INF)cout<<"-1\n"; else { cout<<ans<<'\n'; } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

robots.cpp: In function 'int main()':
robots.cpp:86:73: warning: array subscript has type 'char' [-Wchar-subscripts]
   86 |     g[nxt[i][j][l].first.first][nxt[i][j][l].first.second][nxt[i][j][l].second].push_back({{i,j},l});
      |                                                            ~~~~~~~~~~~~~^~~~~~
robots.cpp:94:50: warning: array subscript has type 'char' [-Wchar-subscripts]
   94 |   actual_nxt[xd.first.first][xd.first.second][xd.second]=xd;
      |                                               ~~~^~~~~~
robots.cpp:100:50: warning: array subscript has type 'char' [-Wchar-subscripts]
  100 |   for(auto xd:g[u.first.first][u.first.second][u.second])
      |                                                ~~^~~~~~
robots.cpp:102:51: warning: array subscript has type 'char' [-Wchar-subscripts]
  102 |    actual_nxt[xd.first.first][xd.first.second][xd.second]=actual_nxt[u.first.first][u.first.second][u.second];
      |                                                ~~~^~~~~~
robots.cpp:102:103: warning: array subscript has type 'char' [-Wchar-subscripts]
  102 |    actual_nxt[xd.first.first][xd.first.second][xd.second]=actual_nxt[u.first.first][u.first.second][u.second];
      |                                                                                                     ~~^~~~~~
robots.cpp:188:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<short int, short int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  188 |    for(int j=0;j<pq[mindp].size();j++)q.push({pq[mindp][j].first,pq[mindp][j].second});
      |                ~^~~~~~~~~~~~~~~~~
robots.cpp:206:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<short int, short int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  206 |      for(int ii=0;ii<pq[dp[cc][x][y]+1].size();ii++)
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
robots.cpp:215:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  215 |    for(int j=0;j<dps.size();j++)pq[dps[j]].clear();
      |                ~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...