제출 #261457

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
261457		brcode	로봇 (APIO13_robots)	C++14	60 / 100	1570 ms	154464 KiB

robots

#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;
         ^~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 0 / 40