제출 #701892

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
701892		Dan4Life	Robots (APIO13_robots)	C++17	60 / 100	1557 ms	100360 KiB

robots

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
using pii = pair<int,int>;
const int mxN = (int)5e2+10;
const int LINF = (int)1e8;
int n, w, h;
string a[mxN];
pii mov[5][mxN][mxN];
int X[] = {-1,0,1,0};
int Y[] = {0,1,0,-1};
bool vis[10][10][mxN][mxN];
int dp[10][10][mxN][mxN];

inline bool isValid(int x, int y){ return (x>=0 and x<h and y>=0 and y<w and a[x][y]!='x'); }

pii mv(int dir, int x,int y){
    while(isValid(x,y)){
        if(a[x][y]=='A') dir=(dir+3)%4;
        else if(a[x][y]=='C') dir=(dir+1)%4;
        if(!isValid(x+X[dir], y+Y[dir])) break;
        x+=X[dir], y+=Y[dir];
    }
    return mp(x,y);
}

int32_t main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> w >> h; int ans = LINF;
    for(int i = 0; i < h; i++) cin >> a[i];
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            for(int k = 0; k <= h; k++)
                for(int l = 0; l <= w; l++)
                    dp[i][j][k][l]=LINF;   
    for(int k = 0; k < 4; k++)
        for(int i = 0; i < h; i++)
            for(int j = 0; j < w; j++)
                mov[k][i][j] = mv(k,i,j);
    for(int i = 0; i < h; i++)
        for(int j = 0; j < w; j++)
            if(a[i][j]>='0' and a[i][j]<='9')
                dp[a[i][j]-'0'][a[i][j]-'0'][i][j]=0;
    priority_queue<pair<int,pair<int,int>>> pq; 
    for(int l = 1; l <= n; l++){
        for(int i=1,j=i+l-1;j<=n;i++,j++){
            for(int x = 0; x < h; x++){
                for(int y = 0; y < w; y++){
                    for(int k = i; k < j; k++)
                        dp[i][j][x][y] = min(dp[i][j][x][y], 
                            dp[i][k][x][y]+dp[k+1][j][x][y]);
                    pq.push({-dp[i][j][x][y], mp(x,y)});
                }
            }
            while(!pq.empty()){
                auto cur = pq.top().se; pq.pop();
                int x = cur.fi, y = cur.se;
                if(vis[i][j][x][y]) continue; vis[i][j][x][y]=1;
                for(int k = 0; k < 4; k++){
                    int nx = mov[k][x][y].fi, ny = mov[k][x][y].se;
                    if(dp[i][j][x][y]+1< dp[i][j][nx][ny]){
                        dp[i][j][nx][ny]=dp[i][j][x][y]+1;
                        pq.push({-dp[i][j][nx][ny], mp(nx,ny)});
                    }
                }
            }
        }
    }
    for(int x = 0; x < h; x++)
        for(int y = 0; y < w; y++)
            ans = min(ans, dp[1][n][x][y]);
    cout << (ans==LINF?-1:ans);
}

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

robots.cpp: In function 'int32_t main()':
robots.cpp:63:17: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   63 |                 if(vis[i][j][x][y]) continue; vis[i][j][x][y]=1;
      |                 ^~
robots.cpp:63:47: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   63 |                 if(vis[i][j][x][y]) continue; vis[i][j][x][y]=1;
      |                                               ^~~

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