Submission #72163

#	Time	Username	Problem	Language	Result	Execution time	Memory
72163		cat > /dev/null (#118)	Aquatic Labyrinth (FXCUP3_aqua)	C++17	100 / 100	332 ms	5096 KiB

aqua

#include <cstdio>
#include <queue>
#define N 910
#define INF 0x3fffffff

using namespace std;

int n;
int d[N][N];
char map[N][N];
int dx[]={-1,0,1,0}, dy[]={0,-1,0,1};

struct st
{
    int x, y, e;
    bool operator<(const st &hs) const
    {
        return e>hs.e;
    }
    bool in_bound()
    {
        return 0<=x && x<n && 0<=y && y<n;
    }
    void move(int way)
    {
        x += dx[way];
        y += dy[way];
    }
    char state()
    {
        return map[x][y];
    }
};
priority_queue<st> q;
st m, h;

int main()
{
    scanf("%d", &n);
    for(int i=0; i<n; ++i)
    {
        scanf("%s", map[i]);
        for(int j=0; j<n; ++j)
        {
            d[i][j] = INF;
            if(map[i][j] == 'M')
                m = {i, j, 0};
            if(map[i][j] == 'H')
                h = {i, j, 0};
        }
    }
    
    q.push(m);
    d[m.x][m.y] = 1;
    while(!q.empty())
    {
        st now = q.top();
        q.pop();
        if(d[now.x][now.y] <= now.e)
            continue;
        d[now.x][now.y] = now.e;
        if(now.x==h.x && now.y==h.y)
            break;
        
        for(int w=0; w<4; ++w)
        {
            st wall = now;
            while(wall.in_bound() && wall.state()!='W')
                wall.move(w);
            
            if(wall.in_bound())
            {
                int dep;
                for(dep=0; wall.in_bound() && wall.state()=='W'; ++dep)
                    wall.move(w);
                
                if(wall.in_bound())
                    while(wall.in_bound() && wall.state()!='W')
                    {
                        if(d[wall.x][wall.y] > now.e+dep*dep)
                        {
                            d[wall.x][wall.y] = now.e+dep*dep+1;
                            q.push({wall.x, wall.y, now.e+dep*dep});
                        }
                        wall.move(w);
                    }
            }
        }
    }
    
    printf("%d", d[h.x][h.y]==INF? -1 : d[h.x][h.y]);
    return 0;
}

Compilation message (stderr)

aqua.cpp: In function 'int main()':
aqua.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
aqua.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", map[i]);
         ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 36 / 36
• Subtask 2: 64 / 64