Submission #549060

#	Time	Username	Problem	Language	Result	Execution time	Memory
549060		Amylopectin	Portals (BOI14_portals)	C++14	100 / 100	257 ms	53740 KiB

portals

#include <iostream>
#include <stdio.h>
#include <queue>
#include <limits.h>

using namespace std;
const int mxn = 1010,dn[4] = {0,0,1,-1},dm[4] = {1,-1,0,0},mav = INT_MAX;
struct we
{
    int nn,mm,dis;
    bool operator () (const struct we &l,const struct we &r)
    {
        return l.dis > r.dis;
    }
};
struct pp
{
    int nn,mm;
};
queue <struct we> fq;
priority_queue<struct we, vector<struct we>,struct we> qu;
struct pp jn[4][mxn][mxn] = {};
int fw[mxn][mxn] = {},u[mxn][mxn] = {},di[mxn][mxn] = {};
char s[mxn][mxn] = {};
int main()
{
    int i,j,n,m,stn,stm,cn,cm,fn,fm,tn,tm,cdi,fdi,k,o,sta,of;
    scanf("%d %d",&n,&m);
    for(i=0; i<n; i++)
    {
        scanf("%s",&s[i]);
//        for(j=0; j<m; j++)
//        {
//            if(s[i][j] == 'S')
//            {
//                stn = i;
//                stm = j;
//            }
//        }
    }
    for(i=0; i<n; i++)
    {
        for(j=0; j<m; j++)
        {
            di[i][j] = mav;
            if(s[i][j] == 'S')
            {
                stn = i;
                stm = j;
            }
            if(s[i][j] != '#')
            {
                if(i == 0 || i == n-1 || j == 0 || j == m-1 || s[i-1][j] == '#' || s[i+1][j] == '#' || s[i][j-1] == '#' || s[i][j+1] == '#')
                {
                    fq.push({i,j,0});
                    fw[i][j] = 0;
                    u[i][j] = 1;
                }
            }
        }
    }
    while(!fq.empty())
    {
        cn = fq.front().nn;
        cm = fq.front().mm;
        cdi = fq.front().dis;
        fq.pop();
        for(i=0; i<4; i++)
        {
            fn = cn + dn[i];
            fm = cm + dm[i];
            if(fn < 0 || fn > n-1 || fm < 0 || fm > m-1 || s[fn][fm] == '#' || u[fn][fm] == 1)
                continue;
            u[fn][fm] = 1;
            fw[fn][fm] = cdi + 1;
            fq.push({fn,fm,cdi + 1});
        }
    }
    for(i=0; i<n; i++)
    {
        sta = 0;
        for(j=0; j<m; j++)
        {
            if(sta == 0)
            {
                if(s[i][j] != '#')
                {
                    cn = i;
                    cm = j;
                    sta = 1;
                    jn[0][i][j] = {cn,cm};
                }
            }
            else
            {
                if(s[i][j] != '#')
                {
                    jn[0][i][j] = {cn,cm};
                }
                else
                {
                    sta = 0;
                }
            }
        }
    }
    for(i=0; i<n; i++)
    {
        sta = 0;
        for(j=m-1; j>=0; j--)
        {
            if(sta == 0)
            {
                if(s[i][j] != '#')
                {
                    cn = i;
                    cm = j;
                    sta = 1;
                    jn[1][i][j] = {cn,cm};
                }
            }
            else
            {
                if(s[i][j] != '#')
                {
                    jn[1][i][j] = {cn,cm};
                }
                else
                {
                    sta = 0;
                }
            }
        }
    }
    for(j=0; j<m; j++)
    {
        sta = 0;
        for(i=0; i<n; i++)
        {
            if(sta == 0)
            {
                if(s[i][j] != '#')
                {
                    cn = i;
                    cm = j;
                    sta = 1;
                    jn[2][i][j] = {cn,cm};
                }
            }
            else
            {
                if(s[i][j] != '#')
                {
                    jn[2][i][j] = {cn,cm};
                }
                else
                {
                    sta = 0;
                }
            }
        }
    }
    for(j=0; j<m; j++)
    {
        sta = 0;
        for(i=n-1; i>=0; i--)
        {
            if(sta == 0)
            {
                if(s[i][j] != '#')
                {
                    cn = i;
                    cm = j;
                    sta = 1;
                    jn[3][i][j] = {cn,cm};
                }
            }
            else
            {
                if(s[i][j] != '#')
                {
                    jn[3][i][j] = {cn,cm};
                }
                else
                {
                    sta = 0;
                }
            }
        }
    }
    qu.push({stn,stm,0});
    di[stn][stm] = 0;
    while(!qu.empty())
    {
        cn = qu.top().nn;
        cm = qu.top().mm;
        cdi = qu.top().dis;
        qu.pop();
        if(di[cn][cm] != cdi)
            continue;
        if(s[cn][cm] == 'C')
            break;
        for(i=0; i<4; i++)
        {
            fn = cn + dn[i];
            fm = cm + dm[i];
            if(fn < 0 || fn >= n || fm < 0 || fm >= m || s[fn][fm] == '#' || cdi + 1 >= di[fn][fm])
            {
                continue;
            }
            di[fn][fm] = cdi + 1;
            qu.push({fn,fm,cdi + 1});
        }
        for(i=0; i<4; i++)
        {
            fn = jn[i][cn][cm].nn;
            fm = jn[i][cn][cm].mm;
            if(cdi + 1 + fw[cn][cm] < di[fn][fm])
            {
                di[fn][fm] = cdi + 1 + fw[cn][cm];
                qu.push({fn,fm,di[fn][fm]});
            }
        }
    }
    printf("%d\n",cdi);
    return 0;
}

Compilation message (stderr)

portals.cpp: In function 'int main()':
portals.cpp:31:17: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[1010]' [-Wformat=]
   31 |         scanf("%s",&s[i]);
      |                ~^  ~~~~~
      |                 |  |
      |                 |  char (*)[1010]
      |                 char*
portals.cpp:27:37: warning: unused variable 'tn' [-Wunused-variable]
   27 |     int i,j,n,m,stn,stm,cn,cm,fn,fm,tn,tm,cdi,fdi,k,o,sta,of;
      |                                     ^~
portals.cpp:27:40: warning: unused variable 'tm' [-Wunused-variable]
   27 |     int i,j,n,m,stn,stm,cn,cm,fn,fm,tn,tm,cdi,fdi,k,o,sta,of;
      |                                        ^~
portals.cpp:27:47: warning: unused variable 'fdi' [-Wunused-variable]
   27 |     int i,j,n,m,stn,stm,cn,cm,fn,fm,tn,tm,cdi,fdi,k,o,sta,of;
      |                                               ^~~
portals.cpp:27:51: warning: unused variable 'k' [-Wunused-variable]
   27 |     int i,j,n,m,stn,stm,cn,cm,fn,fm,tn,tm,cdi,fdi,k,o,sta,of;
      |                                                   ^
portals.cpp:27:53: warning: unused variable 'o' [-Wunused-variable]
   27 |     int i,j,n,m,stn,stm,cn,cm,fn,fm,tn,tm,cdi,fdi,k,o,sta,of;
      |                                                     ^
portals.cpp:27:59: warning: unused variable 'of' [-Wunused-variable]
   27 |     int i,j,n,m,stn,stm,cn,cm,fn,fm,tn,tm,cdi,fdi,k,o,sta,of;
      |                                                           ^~
portals.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
portals.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         scanf("%s",&s[i]);
      |         ~~~~~^~~~~~~~~~~~
portals.cpp:192:18: warning: 'stm' may be used uninitialized in this function [-Wmaybe-uninitialized]
  192 |     di[stn][stm] = 0;
      |     ~~~~~~~~~~~~~^~~
portals.cpp:192:18: warning: 'stn' may be used uninitialized in this function [-Wmaybe-uninitialized]

• Subtask 1: 11 / 11
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 19 / 19
• Subtask 5: 30 / 30