Submission #422364

#	Time	Username	Problem	Language	Result	Execution time	Memory
422364		Amylopectin	Robots (APIO13_robots)	C++14	100 / 100	628 ms	60112 KiB

robots

#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int mxn = 510,mxm = 90,mxi = 1e9 + 10,mxp = 3e5 + 10,dn[4] = {-1,0,1,0},dm[4] = {0,1,0,-1};
struct we
{
    int nn,mm,dis;
};
bool cmp(const struct we &l,const struct we &r)
{
    return l.dis < r.dis;
}
queue <struct we> qu;
struct we st[mxn] = {};
char s[mxn][mxn] = {};
int di[mxm][mxn][mxn] = {},u[mxn][mxn] = {};
struct we pa[mxn][mxn][4] = {},pli[mxp] = {};
int fima(int l,int r)
{
    if(l > r)
        return l;
    return r;
}
int fimi(int l,int r)
{
    if(l < r)
        return l;
    return r;
}
int main()
{
    int i,j,n,m,ro,cn,cm,fn,fm,cva,k,o,p,f,t,af,cdir,of,cou,cru,cdi,fdi,uc,cmi = mxi;
    scanf("%d %d %d",&ro,&m,&n);
    for(i=0; i<n; i++)
    {
        scanf("%s",&s[i]);
        for(j=0; j<m; j++)
        {
            if(s[i][j] > '0' && s[i][j] <= '9')
            {
                cva = s[i][j] - '1';
                st[cva] = {i,j,0};
            }
        }
    }
    cou = 0;
    for(i=0; i<n; i++)
    {
        for(j=0; j<m; j++)
        {
            for(k=0; k<4; k++)
            {
                cn = i;
                cm = j;
                cdir = k;
                cou ++;
                while(1)
                {
                    of = 0;
                    while(1)
                    {
                        fn = cn+dn[cdir];
                        fm = cm+dm[cdir];
                        if(fn < 0 || fn >= n || fm < 0 || fm >= m || s[fn][fm] == 'x')
                        {
                            of = 1;
                            break;
                        }
                        cn = fn;
                        cm = fm;
                        if(s[cn][cm] == 'C')
                        {
                            cdir = (cdir + 1) % 4;
                            break;
                        }
                        if(s[cn][cm] == 'A')
                        {
                            cdir = (cdir + 3) % 4;
                            break;
                        }
                    }
                    if(u[cn][cm] == cou)
                    {
                        break;
                    }
                    u[cn][cm] = cou;
                    if(of == 1)
                    {
                        break;
                    }
                }
                pa[i][j][k] = {cn,cm,0};
                if(of == 0)
                {
                    pa[i][j][k].dis = -1;
                }
            }
        }
    }
//    uc = 0;
    for(i=0; i<ro; i++)
    {
        for(j=i; j>=0; j--)
        {
            af = j*ro + i;
            for(o=0; o<n; o++)
            {
                for(p=0; p<m; p++)
                {
                    di[af][o][p] = mxi;
                    u[o][p] = 0;
                }
            }
            if(j < i)
            {
                for(k=j; k<i; k++)
                {
                    f = j*ro+k;
                    t = (k+1)*ro + i;
                    for(o=0; o<n; o++)
                    {
                        if(di[f][o][p] != mxi)
                        for(p=0; p<m; p++)
                        {
                            if(di[t][o][p] != mxi)
                            {
                                di[af][o][p] = fimi(di[af][o][p], di[f][o][p] + di[t][o][p]);
                            }
                        }
                    }
                }
                cou = 0;
                for(o=0; o<n; o++)
                {
                    for(p=0; p<m; p++)
                    {
                        if(di[af][o][p] != mxi)
                        {
                            pli[cou] = {o,p,di[af][o][p]};
                            cou ++;
                        }
                    }
                }
                cru = 0;
                sort(pli,pli+cou,cmp);
                cdi = pli[0].dis;
                while(pli[cru].dis == cdi && cru < cou)
                {
                    qu.push(pli[cru]);
                    u[pli[cru].nn][pli[cru].mm] = 1;
                    cru ++;
                }
            }
            else
            {
                di[af][st[i].nn][st[i].mm] = 0;
                qu.push({st[i].nn,st[i].mm,0});
                u[st[i].nn][st[i].mm] = 1;
                cou = 0;
                cru = 0;
            }
            while(!qu.empty())
            {
                cn = qu.front().nn;
                cm = qu.front().mm;
                cdi = qu.front().dis;
                qu.pop();
                while(cru < cou && pli[cru].dis == cdi)
                {
                    fn = pli[cru].nn;
                    fm = pli[cru].mm;
                    if(u[fn][fm] == 0)
                    {
                        u[fn][fm] = 1;
                        qu.push(pli[cru]);
                    }
                    cru ++;
                }
                for(k=0; k<4; k++)
                {
                    if(pa[cn][cm][k].dis == -1)
                    {
                        continue;
                    }
                    fn = pa[cn][cm][k].nn;
                    fm = pa[cn][cm][k].mm;
                    if(u[fn][fm] == 1)
                    {
                        continue;
                    }
                    u[fn][fm] = 1;
                    di[af][fn][fm] = cdi+1;
                    qu.push({fn,fm,cdi+1});
                }
            }
        }
    }
    af = 0*ro + ro-1;
    for(o=0; o<n; o++)
    {
        for(p=0; p<m; p++)
        {
            cmi = fimi(cmi,di[af][o][p]);
        }
    }
    if(cmi != mxi)
    {
        printf("%d\n",cmi);
    }
    else
    {
        printf("-1\n");
    }
    return 0;
}

Compilation message (stderr)

robots.cpp: In function 'int main()':
robots.cpp:39:17: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[510]' [-Wformat=]
   39 |         scanf("%s",&s[i]);
      |                ~^  ~~~~~
      |                 |  |
      |                 |  char (*)[510]
      |                 char*
robots.cpp:35:69: warning: unused variable 'fdi' [-Wunused-variable]
   35 |     int i,j,n,m,ro,cn,cm,fn,fm,cva,k,o,p,f,t,af,cdir,of,cou,cru,cdi,fdi,uc,cmi = mxi;
      |                                                                     ^~~
robots.cpp:35:73: warning: unused variable 'uc' [-Wunused-variable]
   35 |     int i,j,n,m,ro,cn,cm,fn,fm,cva,k,o,p,f,t,af,cdir,of,cou,cru,cdi,fdi,uc,cmi = mxi;
      |                                                                         ^~
robots.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     scanf("%d %d %d",&ro,&m,&n);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
robots.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         scanf("%s",&s[i]);
      |         ~~~~~^~~~~~~~~~~~
robots.cpp:125:38: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
  125 |                         if(di[f][o][p] != mxi)
      |                            ~~~~~~~~~~^

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