제출 #261457

#제출 시각아이디문제언어결과실행 시간메모리
261457brcode로봇 (APIO13_robots)C++14
60 / 100
1570 ms154464 KiB
#include <iostream> #include <bits/stdc++.h> using namespace std; const int MAXN = 510; int grid[MAXN][MAXN]; int dp[MAXN][MAXN][12][12]; vector<pair<int,int>> res[2]; vector<pair<int,pair<int,int>>> v1; int n,h,w; int dx[6] = {0,0,1,0,-1}; int dy[6] = {0,1,0,-1,0}; pair<int,int> visited[MAXN][MAXN][5]; pair<int,int> bot[20]; bool check(int i,int j){ if(i<=0||j<=0||i>w||j>h||grid[i][j] == 0){ return false; } return true; } pair<int,int> dfs(int i,int j,int dir){ if(visited[i][j][dir]!=make_pair(0,0)){ return visited[i][j][dir]; } if(grid[i][j]==1){ int nexti = i+dx[dir]; int nextj = j+dy[dir]; if(check(nexti,nextj)){ return visited[i][j][dir] = dfs(nexti,nextj,dir); }else{ return make_pair(i,j); } } if(grid[i][j]==2){ int newdir = dir; newdir--; if(newdir == 0){ newdir = 4; } int nexti = i+dx[newdir]; int nextj = j+dy[newdir]; if(check(nexti,nextj)){ return visited[i][j][dir] = dfs(nexti,nextj,newdir); }else{ return make_pair(i,j); } } if(grid[i][j]==3){ int newdir = dir; newdir++; if(newdir == 5){ newdir = 1; } int nexti = i+dx[newdir]; int nextj = j+dy[newdir]; if(check(nexti,nextj)){ return visited[i][j][dir] = dfs(nexti,nextj,newdir); }else{ return make_pair(i,j); } } return make_pair(0,0); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin>>n>>w>>h; swap(w,h); int mx = h*w; for(int i=1;i<=w;i++){ for(int j=1;j<=h;j++){ char x; cin>>x; if(x=='.'){ grid[i][j] = 1; continue; } if(x=='x'){ grid[i][j] = 0; continue; } if(x=='A'){ grid[i][j] = 2; continue; } if(x=='C'){ grid[i][j] = 3; continue; } grid[i][j] = 1; int y = x-'0'; bot[y] = make_pair(i,j); } } for(int i=1;i<=w;i++){ for(int j=1;j<=h;j++){ for(int x=1;x<=n;x++){ for(int y=1;y<=n;y++){ dp[i][j][x][y] = 1e9; } } } } for(int i=1;i<=n;i++){ dp[bot[i].first][bot[i].second][i][i] = 0; // cout<<i<<" "<<bot[i].first<<" "<<bot[i].second<<endl; } for(int i=1;i<=w;i++){ for(int j=1;j<=h;j++){ if(grid[i][j] == 0){ continue; } if(visited[i][j][1]== make_pair(0,0)){ dfs(i,j,1); } if(visited[i][j][2]== make_pair(0,0)){ dfs(i,j,2); } if(visited[i][j][3]== make_pair(0,0)){ dfs(i,j,3); } if(visited[i][j][4]== make_pair(0,0)){ dfs(i,j,4); } } } //cout<<visited[5][5][1].first<<" "<<visited[5][5][1].second<<endl; for(int len=0;len<=n-1;len++){ for(int x=1;x<=n;x++){ int y = x+len; if(y>n){ break; } for(int i=1;i<=w;i++){ for(int j=1;j<=h;j++){ for(int z=x;z<y;z++){ if(i==1 && j==1 && x==1 && y==4 && z==2){ //cout<<dp[i][j][z+1][y]<<endl; } dp[i][j][x][y] = min(dp[i][j][x][y],dp[i][j][x][z]+dp[i][j][z+1][y]); } } } res[0].clear(); res[1].clear(); v1.clear(); int holdmx = 0; for(int i=1;i<=w;i++){ for(int j=1;j<=h;j++){ if(dp[i][j][x][y]!=1e9){ v1.push_back(make_pair(dp[i][j][x][y],make_pair(i,j))); holdmx = max(holdmx,dp[i][j][x][y]); } } } sort(v1.begin(),v1.end()); int ptr = 0; for(int i=0;i<=w*h;i++){ while(ptr<v1.size() && v1[ptr].first==i){ res[i&1].push_back(make_pair(v1[ptr].second.first,v1[ptr].second.second)); ptr++; } for(auto tmp:res[i&1]){ int a = tmp.first; int b = tmp.second; for(int dir=1;dir<=4;dir++){ int nxti = visited[a][b][dir].first; int nxtj = visited[a][b][dir].second; if(nxti == a && nxtj == b){ continue; } if(nxti == 0 && nxtj == 0){ continue; } if(dp[nxti][nxtj][x][y]>i+1){ dp[nxti][nxtj][x][y] = i+1; res[(i+1)&1].push_back(make_pair(nxti,nxtj)); } } } res[i&1].clear(); } } } //cout<<visited[1][7][3].first<<" "<<visited[1][7][3].second<<endl; // cout<<dp[1][7][3][4]<<endl; int ans = 1e9; for(int i=1;i<=w;i++){ for(int j=1;j<=h;j++){ ans = min(ans,dp[i][j][1][n]); } } if(ans == 1e9){ ans = -1; } cout<<ans<<'\n'; }

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

robots.cpp: In function 'int main()':
robots.cpp:171:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 while(ptr<v1.size() && v1[ptr].first==i){
                       ~~~^~~~~~~~~~
robots.cpp:76:9: warning: unused variable 'mx' [-Wunused-variable]
     int mx = h*w;
         ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...