Submission #395383

#	Time	Username	Problem	Language	Result	Execution time	Memory
395383		ponkung	Robots (APIO13_robots)	C++14	30 / 100	1590 ms	716 KiB

robots

#include<bits/stdc++.h>
using namespace std;
int robots,n,m,st_x,st_y,ed_x,ed_y,d[15][15][15][15],dx[]={-1,0,1,0},dy[]={0,1,0,-1},x,y,dir,u1,v1,u2,v2,mn=1e9,w1,w2;
char s[505][505];
queue<tuple<int,int,int,int> > q;
struct node
{
    int x,y;
};
node path[15][15][4];
int main()
{
    scanf("%d%d%d",&robots,&m,&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",s[i]+1);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(s[i][j]=='1')
            {
                st_x=i;
                st_y=j;
            }else if(s[i][j]=='2')
            {
                ed_x=i;
                ed_y=j;
            }
        }
    }
    memset(d,-1,sizeof d);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            for(int k=0;k<4;k++)
            {
                x=i;
                y=j;
                dir=k;
                while(1)
                {
                    //printf("%d %d %d\n",x,y,dir);
                    if(x+dx[dir]>=1&&x+dx[dir]<=n&&y+dy[dir]>=1&&y+dy[dir]<=m)
                    {
                        if(s[x+dx[dir]][y+dy[dir]]=='x')
                        {
                            path[i][j][k].x=x;
                            path[i][j][k].y=y;
                            break;
                        }else
                        {
                            x+=dx[dir];
                            y+=dy[dir];
                            if(s[x][y]=='C')
                            {
                                dir=(dir+1)%4;
                            }else if(s[x][y]=='A')
                            {
                                dir=(dir+3)%4;
                            }
                        }
                    }else
                    {
                        path[i][j][k].x=x;
                        path[i][j][k].y=y;
                        break;
                    }
                }
            }
            //printf("%d %d\n",x,y);
        }
    }
    /*for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            for(int k=0;k<4;k++)
            {
                printf("%d %d %d %d %d\n",i,j,k,path[i][j][k].x,path[i][j][k].y);
            }
        }
    }*/
    d[st_x][st_y][ed_x][ed_y]=0;
    //printf("%d %d %d %d\n",st_x,st_y,ed_x,ed_y);
    q.push(make_tuple(st_x,st_y,ed_x,ed_y));
    while(!q.empty())
    {
        u1=get<0>(q.front());
        v1=get<1>(q.front());
        u2=get<2>(q.front());
        v2=get<3>(q.front());
        q.pop();
        for(int i=0;i<4;i++)
        {
            w1=path[u1][v1][i].x;
            w2=path[u1][v1][i].y;
            if(d[w1][w2][u2][v2]==-1)
            {
                d[w1][w2][u2][v2]=d[u1][v1][u2][v2]+1;
                q.push(make_tuple(w1,w2,u2,v2));
            }
        }
        for(int i=0;i<4;i++)
        {
            w1=path[u2][v2][i].x;
            w2=path[u2][v2][i].y;
            if(d[u1][v1][w1][w2]==-1)
            {
                d[u1][v1][w1][w2]=d[u1][v1][u2][v2]+1;
                q.push(make_tuple(u1,v1,w1,w2));
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(d[i][j][i][j]!=-1)
            {
                mn=min(mn,d[i][j][i][j]);
            }
        }
    }
    if(mn==1e9)
    {
        printf("-1\n");
    }else
    {
        printf("%d\n",mn);
    }
}

Compilation message (stderr)

robots.cpp: In function 'int main()':
robots.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   13 |     scanf("%d%d%d",&robots,&m,&n);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
robots.cpp:16:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   16 |         scanf("%s",s[i]+1);
      |         ~~~~~^~~~~~~~~~~~~

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