제출 #234001

#제출 시각아이디문제언어결과실행 시간메모리
234001AQT로봇 (APIO13_robots)C++14
60 / 100
555 ms163844 KiB
#pragma GCC optimize ("O3") #pragma GCC target ("sse4") // Problem : APIO '13 P1 - Robots // Contest : DMOJ // URL : https://dmoj.ca/problem/apio13p1 // Memory Limit : 128 MB // Time Limit : 750 ms // Powered by CP Editor (https://github.com/cpeditor/cpeditor) #include <bits/stdc++.h> using namespace std; int K, N, M; int dist[10][10][505][505]; vector<pair<int, int>> graph[505][505]; char mp[505][505]; pair<int, int> moves[4] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; pair<int, int> endpos[4][505][505]; vector<pair<int, int>> vec[505*505*10]; int oo = INT_MAX>>2; pair<int, int> fnd(int d, int x, int y){ if(endpos[d][x][y].first){ return endpos[d][x][y]; } int r = 0; if(mp[x][y] == 'A'){ r = 3; } if(mp[x][y] == 'C'){ r = 1; } if(mp[x+moves[(d+r)%4].first][y+moves[(d+r)%4].second] == 'x'){ return endpos[d][x][y] = {x, y}; } return endpos[d][x][y] = fnd((d+r)%4, x+moves[(d+r)%4].first, y+moves[(d+r)%4].second); } int main(){ cin.sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> K >> M >> N; oo = K*M*N; for(int l = 1; l<=K; l++){ for(int r = l; r<=K; r++){ for(int i = 1; i<=N; i++){ for(int j = 1; j<=M; j++){ dist[l][r][i][j] = oo; } } } } for(int i = 1; i<=N; i++){ for(int j = 1; j<=M; j++){ cin >> mp[i][j]; if(mp[i][j] > '0' && mp[i][j] <= '9'){ dist[mp[i][j]-'0'][mp[i][j]-'0'][i][j] = 0; } } } for(int i = 0; i<=N+1; i++){ mp[i][0] = mp[i][M+1] = 'x'; } for(int j = 0; j<=M+1; j++){ mp[0][j] = mp[N+1][j] = 'x'; } for(int i = 1; i<=N; i++){ for(int j = 1; j<=M; j++){ for(int k = 0; k<4; k++){ graph[i][j].push_back(fnd(k, i, j)); } } } for(int len = 1; len<=K; len++){ for(int l = 1; l+len-1<=K; l++){ int r = l+len-1; for(int i = 1; i<=N; i++){ for(int j = 1; j<=M; j++){ for(int k = l; k<r; k++){ dist[l][r][i][j] = min(dist[l][k][i][j] + dist[k+1][r][i][j], dist[l][r][i][j]); } if(dist[l][r][i][j] != oo){ //pq.push({dist[l][r][i][j], {i, j}}); vec[dist[l][r][i][j]].emplace_back(i, j); } } } /* while(pq.size()){ auto p = pq.top(); pq.pop(); if(dist[l][r][p.second.first][p.second.second] != p.first){ continue; } for(auto e : graph[p.second.first][p.second.second]){ if(dist[l][r][e.first][e.second] > dist[l][r][p.second.first][p.second.second] + 1){ dist[l][r][e.first][e.second] = dist[l][r][p.second.first][p.second.second] + 1; pq.push({dist[l][r][e.first][e.second], {e.first, e.second}}); } } } */ for(int d = 0; d<=oo; d++){ for(auto p : vec[d]){ if(dist[l][r][p.first][p.second] != d){ continue; } for(auto e : graph[p.first][p.second]){ if(dist[l][r][e.first][e.second] > d+1){ dist[l][r][e.first][e.second] = d+1; vec[d+1].emplace_back(e.first, e.second); } } } } } } int ans = oo; for(int i = 1; i<=N; i++){ for(int j = 1; j<=M; j++){ ans = min(dist[1][K][i][j], ans); } } /* for(int l = 1; l<=K; l++){ for(int r = l; r<=K; r++){ cout << l << " " << r << "\n"; for(int i = 1; i<=N; i++){ for(int j = 1; j<=M; j++){ if(dist[l][r][i][j] == INT_MAX>>2){ cout << 'X'; } else{ cout << dist[l][r][i][j]; } } cout << "\n"; } cout << "\n"; } } */ cout << (ans == oo ? -1 : ans); }

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

robots.cpp: In function 'int main()':
robots.cpp:82:60: warning: array subscript is above array bounds [-Warray-bounds]
       dist[l][r][i][j] = min(dist[l][k][i][j] + dist[k+1][r][i][j], dist[l][r][i][j]);
                                                 ~~~~~~~~~~~^
robots.cpp:82:57: warning: array subscript is above array bounds [-Warray-bounds]
       dist[l][r][i][j] = min(dist[l][k][i][j] + dist[k+1][r][i][j], dist[l][r][i][j]);
                                                 ~~~~~~~~^
robots.cpp:82:16: warning: array subscript is above array bounds [-Warray-bounds]
       dist[l][r][i][j] = min(dist[l][k][i][j] + dist[k+1][r][i][j], dist[l][r][i][j]);
       ~~~~~~~~~^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...