제출 #40407

#제출 시각아이디문제언어결과실행 시간메모리
40407mohammad_kilani로봇 (APIO13_robots)C++14
60 / 100
474 ms121032 KiB
#include <bits/stdc++.h> using namespace std; #define mod 1000000007 #define oo 1000000000 const double PI = acos(-1); const int N = 501 , MAX_COST = 500 * 30 * 9 + 1; char grid[N][N]; int n , m , sr , sc, cnt = 0 , idx[10][10] , num , vis[N][N] , vi = 1 , row , col , nr ,nc , cost , best[50][N][N]; int dr[4] = {1,0,-1,0}; int dc[4] = {0,1,0,-1}; pair<int,int> nxt[N][N][4]; vector< vector< pair<int,int> > > tmp2; vector< pair<int,pair<int,int> > > tmp; deque < pair<int, pair<int,int> > > q; inline void BFS(int low,int high){ vi++; tmp.clear(); tmp2.clear(); tmp2.resize(MAX_COST); for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(best[idx[low][high]][i][j] == oo) continue; tmp2[best[idx[low][high]][i][j]].push_back(make_pair(i,j)); } } for(int i=0;i<MAX_COST;i++) for(int j=0;j<tmp2[i].size();j++){ tmp.push_back(make_pair(i,tmp2[i][j])); } for(int i=0;i<tmp.size();i++){ q.push_back(tmp[i]); while(!q.empty()){ cost = q.back().first; row = q.back().second.first; col = q.back().second.second; q.pop_back(); if(vis[row][col] == vi) continue; vis[row][col] = vi; best[idx[low][high]][row][col] = cost; while(i + 1 < tmp.size() && tmp[i + 1].first == cost){ i++; if(vis[tmp[i].second.first][tmp[i].second.second] == vi) continue; q.push_back(tmp[i]); } for(int i=0;i<4;i++){ nr = nxt[row][col][i].first; nc = nxt[row][col][i].second; if(nr == -1 || vis[nr][nc] == vi) continue; q.push_front(make_pair(cost + 1 , make_pair(nr,nc))); } } } } inline void make(int r,int c,int k){ sr = r; sc = c; while(r >= 0 && r < n && c >= 0 && c < m && grid[r][c] != 'x'){ if(grid[r][c] == 'A') k--; else if(grid[r][c] == 'C') k++; if(k == -1) k = 3; if(k == 4) k = 0; nxt[r][c][k] = make_pair(sr,sc); r = r + dr[k]; c = c + dc[k]; } } int main(){ for(int i=1;i<10;i++){ for(int j=i;j<10;j++){ idx[i][j] = cnt++; } } scanf("%d%d%d",&num,&m,&n); for(int i=0;i<cnt;i++){ for(int j=0;j<n;j++){ for(int k=0;k<m;k++){ best[i][j][k] = oo; } } } for(int i=0;i<n;i++) scanf("%s",grid[i]); for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(grid[i][j] >= '1' && grid[i][j] <= '9'){ best[idx[grid[i][j]-'0'][grid[i][j]-'0']][i][j] = 0; } for(int k=0;k<4;k++) nxt[i][j][k] = make_pair(-1,-1); } } for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(grid[i][j] == 'x') continue; sr = i; sc = j; for(int k=0;k<4;k++){ int nr = i + dr[k]; int nc = j + dc[k]; if(nr == -1 || nr == n || nc == -1 || nc == m || grid[nr][nc] == 'x'){ make(i,j,(k + 2) % 4); } } } } for(int i=0;i<num;i++){ for(int j=1;j+i<=num;j++){ for(int row=0;row<n;row++){ for(int col=0;col<m;col++){ for(int k=j;k<j+i;k++){ best[idx[j][i+j]][row][col] = min(best[idx[j][i+j]][row][col],best[idx[j][k]][row][col] + best[idx[k+1][i+j]][row][col]); } } } BFS(j,j+i); } } int ans = oo; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ ans = min(ans,best[idx[1][num]][i][j]); } } if(ans == oo) ans = -1; cout << ans << endl; return 0; }

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

robots.cpp: In function 'void BFS(int, int)':
robots.cpp:28:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<tmp2[i].size();j++){
                ^
robots.cpp:31:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<tmp.size();i++){
               ^
robots.cpp:41:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(i + 1 < tmp.size() && tmp[i + 1].first == cost){
                ^
robots.cpp: In function 'int main()':
robots.cpp:75:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&num,&m,&n);
                            ^
robots.cpp:84:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",grid[i]);
                      ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...