Submission #155718

#	Time	Username	Problem	Language	Result	Execution time	Memory
155718		arnold518	Robots (APIO13_robots)	C++14	30 / 100	233 ms	40228 KiB

robots

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 500;
const int INF = 987654321;

const int dy[]={-1, 1, 0, 0};
const int dx[]={0, 0, -1, 1};
const int dA[]={2, 3, 1, 0};
const int dC[]={3, 2, 0, 1};

int N, W, H;
char A[MAXN+10][MAXN+10];
pii dest[MAXN+10][MAXN+10][4];
int dp[MAXN+10][MAXN+10][10][10];

void dfs(int y, int x, int dir)
{
    if(dest[y][x][dir]!=pii(-1, -1)) return;
    int ndir;
    if(A[y][x]=='A') ndir=dA[dir];
    else if(A[y][x]=='C') ndir=dC[dir];
    else ndir=dir;

    int ny=y+dy[ndir], nx=x+dx[ndir];
    if(A[ny][nx]=='x')
    {
        dest[y][x][dir]={y, x};
        return;
    }
    dfs(ny, nx, ndir);
    dest[y][x][dir]=dest[ny][nx][ndir];
}

struct Queue
{
    int y, x, w;
    bool operator < (const Queue &p) const { return w<p.w; }
};

int main()
{
    int i, j, k, p, q;

    scanf("%d%d%d", &N, &W, &H);
    for(i=1; i<=H; i++) scanf("%s", A[i]+1);
    for(i=0; i<=H+1; i++) A[i][0]=A[i][W+1]='x';
    for(j=0; j<=W+1; j++) A[0][j]=A[H+1][j]='x';

    for(i=1; i<=H; i++) for(j=1; j<=W; j++) for(k=0; k<4; k++) dest[i][j][k]={-1, -1};
    for(i=1; i<=H; i++) for(j=1; j<=W; j++) for(k=0; k<4; k++)
    {
        if(dest[i][j][k]!=pii(-1, -1)) continue;
        dfs(i, j, k);
    }
    //for(i=1; i<=H; i++) { for(j=1; j<=W; j++) printf("(%d %d / %d %d / %d %d / %d %d) ", dest[i][j][0].first, dest[i][j][0].second, dest[i][j][1].first, dest[i][j][1].second, dest[i][j][2].first, dest[i][j][2].second, dest[i][j][3].first, dest[i][j][3].second); printf("\n"); }

    for(q=1; q<=N; q++) for(p=q; p>=1; p--)
    {
        Queue start={0, 0, INF+1};
        for(i=1; i<=H; i++) for(j=1; j<=W; j++) dp[i][j][p][q]=INF;
        if(p==q)
        {
            for(i=1; i<=H; i++) for(j=1; j<=W; j++)
            {
                int now;
                if(A[i][j]=='0'+p) now=0;
                else now=INF;
                dp[i][j][p][q]=now;
                start=min(start, {i, j, now});
            }
        }
        else
        {
            for(i=1; i<=H; i++) for(j=1; j<=W; j++)
            {
                int now=INF;
                for(k=p; k<q; k++)
                {
                    now=min(now, dp[i][j][p][k]+dp[i][j][k+1][q]);
                }
                dp[i][j][p][q]=now;
                start=min(start, {i, j, now});
            }
        }

        queue<Queue> Q;
        Q.push(start);

        while(!Q.empty())
        {
            Queue T=Q.front(); Q.pop();
            //printf("!%d %d %d\n", T.x, T.y, T.w);
            dp[T.y][T.x][p][q]=min(dp[T.y][T.x][p][q], T.w);
            for(k=0; k<4; k++) if(dp[dest[T.y][T.x][k].first][dest[T.y][T.x][k].second][p][q]>dp[T.y][T.x][p][q]+1) Q.push({dest[T.y][T.x][k].first, dest[T.y][T.x][k].second, dp[T.y][T.x][p][q]+1}); //printf("?%d %d %d\n", dest[T.y][T.x][k].first, dest[T.y][T.x][k].second, T.w+1);
        }
        //printf("=======%d %d========\n", p, q);
        //for(i=1; i<=H; i++) { for(j=1; j<=W; j++) printf("%d ", dp[i][j][p][q]); printf("\n"); }
    }
    int ans=INF;
    for(i=1; i<=H; i++) for(j=1; j<=W; j++) ans=min(ans, dp[i][j][1][N]);
    if(ans==INF) printf("-1");
    else printf("%d", ans);
}

Compilation message (stderr)

robots.cpp: In function 'int main()':
robots.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &N, &W, &H);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
robots.cpp:50:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1; i<=H; i++) scanf("%s", A[i]+1);
                         ~~~~~^~~~~~~~~~~~~~

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