답안 #72163

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
72163	2018-08-26T05:38:44 Z	cat > /dev/null(#2231, lobo_prix, jms100300, enochjung)	수중 미로 (FXCUP3_aqua)	C++17	100 / 100	332 ms	5096 KB

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

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

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	248 KB	Output is correct
2	Correct	3 ms	500 KB	Output is correct
3	Correct	3 ms	576 KB	Output is correct
4	Correct	2 ms	752 KB	Output is correct
5	Correct	3 ms	780 KB	Output is correct
6	Correct	4 ms	1020 KB	Output is correct
7	Correct	4 ms	1020 KB	Output is correct
8	Correct	5 ms	1024 KB	Output is correct
9	Correct	4 ms	1024 KB	Output is correct
10	Correct	3 ms	1024 KB	Output is correct

Subtask #2

64.0 / 64.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	248 KB	Output is correct
2	Correct	3 ms	500 KB	Output is correct
3	Correct	3 ms	576 KB	Output is correct
4	Correct	2 ms	752 KB	Output is correct
5	Correct	3 ms	780 KB	Output is correct
6	Correct	4 ms	1020 KB	Output is correct
7	Correct	4 ms	1020 KB	Output is correct
8	Correct	5 ms	1024 KB	Output is correct
9	Correct	4 ms	1024 KB	Output is correct
10	Correct	3 ms	1024 KB	Output is correct
11	Correct	22 ms	2240 KB	Output is correct
12	Correct	29 ms	3264 KB	Output is correct
13	Correct	196 ms	4352 KB	Output is correct
14	Correct	18 ms	4352 KB	Output is correct
15	Correct	8 ms	4352 KB	Output is correct
16	Correct	124 ms	5084 KB	Output is correct
17	Correct	332 ms	5096 KB	Output is correct
18	Correct	58 ms	5096 KB	Output is correct
19	Correct	193 ms	5096 KB	Output is correct
20	Correct	16 ms	5096 KB	Output is correct