제출 #72104

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
72104		신딩없는 신딩팀 (#118)	수중 미로 (FXCUP3_aqua)	C++17	100 / 100	1430 ms	255112 KiB

aqua

#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>
#define LL long long
#define INF 1e18
using namespace std;

struct xyw{
    LL x,y,w;

    bool operator>(const xyw A)const{
        return w>A.w;
    }
};

bool mp[999][999];
LL dist[999][999];

vector<xyw> edge[999][999];
priority_queue<xyw,vector<xyw>,greater<xyw> > pq;

vector<int> st;

int main(){
    int n;
    int sx,sy,ex,ey;

    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            char c;
            scanf(" %c",&c);

            if(c=='W') mp[i][j]=1;
            if(c=='H') ex=i,ey=j;
            if(c=='M') sx=i,sy=j;
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int pos=i+1,cnt=0;
            while(pos<=n && !mp[pos][j]) pos++;
            while(pos<=n && mp[pos][j]) pos++,cnt++;
            while(pos<=n && !mp[pos][j]) edge[i][j].push_back({pos++,j,cnt*cnt});

            pos=i-1,cnt=0;
            while(pos>0 && !mp[pos][j]) pos--;
            while(pos>0 && mp[pos][j]) pos--,cnt++;
            while(pos>0 && !mp[pos][j]) edge[i][j].push_back({pos--,j,cnt*cnt});

            pos=j+1,cnt=0;
            while(pos<=n && !mp[i][pos]) pos++;
            while(pos<=n && mp[i][pos]) pos++,cnt++;
            while(pos<=n && !mp[i][pos]) edge[i][j].push_back({i,pos++,cnt*cnt});

            pos=j-1,cnt=0;
            while(pos>0 && !mp[i][pos]) pos--;
            while(pos>0 && mp[i][pos]) pos--,cnt++;
            while(pos>0 && !mp[i][pos]) edge[i][j].push_back({i,pos--,cnt*cnt});
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++) dist[i][j]=INF;
    }
    dist[sx][sy]=0;

    pq.push({sx,sy,0});
    while(!pq.empty()){
        int px=pq.top().x;
        int py=pq.top().y;
        int pw=pq.top().w;
        pq.pop();

        if(px==ex && py==ey){
            printf("%lld",dist[ex][ey]);
            return 0;
        }
        if(pw!=dist[px][py]) continue;

        for(xyw it:edge[px][py]){
            if(dist[it.x][it.y]>dist[px][py]+it.w){
                dist[it.x][it.y]=dist[px][py]+it.w;
                pq.push({it.x,it.y,dist[it.x][it.y]});
            }
        }
    }

    printf("-1");

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

aqua.cpp: In function 'int main()':
aqua.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
aqua.cpp:33:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf(" %c",&c);
             ~~~~~^~~~~~~~~~
aqua.cpp:78:19: warning: 'ex' may be used uninitialized in this function [-Wmaybe-uninitialized]
             printf("%lld",dist[ex][ey]);
             ~~~~~~^~~~~~~~~~~~~~~~~~~~~
aqua.cpp:70:12: warning: 'sy' may be used uninitialized in this function [-Wmaybe-uninitialized]
     pq.push({sx,sy,0});
     ~~~~~~~^~~~~~~~~~~
aqua.cpp:78:19: warning: 'ey' may be used uninitialized in this function [-Wmaybe-uninitialized]
             printf("%lld",dist[ex][ey]);
             ~~~~~~^~~~~~~~~~~~~~~~~~~~~
aqua.cpp:70:12: warning: 'sx' may be used uninitialized in this function [-Wmaybe-uninitialized]
     pq.push({sx,sy,0});
     ~~~~~~~^~~~~~~~~~~

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