oj.uz

Submission #395383

# Submission time Handle Problem Language Result Execution time Memory
395383 2021-04-28T09:56:36 Z ponkung Robots (APIO13_robots) C++14
30 / 100
 1500 ms 716 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 444 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 444 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Execution timed out 1590 ms 716 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 444 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Execution timed out 1590 ms 716 KB Time limit exceeded
12 Halted 0 ms 0 KB -