Submission #72058

#	Time	Username	Problem	Language	Result	Execution time	Memory
72058		신딩없는 신딩팀 (#118)	Aquatic Labyrinth (FXCUP3_aqua)	C++17	0 / 100	23 ms	23908 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++){
        int cnt=0;
        bool sta=1-mp[i][1];

        for(int j=1;j<=n;j++){
            if(mp[i][j]) sta=0,cnt++;
            if(!sta && !mp[i][j]){
                while(!st.empty()){
                    edge[i][st.back()].push_back({i,j,cnt*cnt});
                    st.pop_back();
                }
                sta=1,cnt=0;
            }

            if(sta) st.push_back(j);
        }
        while(!st.empty()) st.pop_back();
    }

    for(int i=1;i<=n;i++){
        int cnt=0;
        bool sta=1-mp[i][n];

        for(int j=n;j>=1;j--){
            if(mp[i][j]) sta=0,cnt++;
            if(!sta && !mp[i][j]){
                while(!st.empty()){
                    edge[i][st.back()].push_back({i,j,cnt*cnt});
                    st.pop_back();
                }
                sta=1,cnt=0;
            }

            if(sta) st.push_back(j);
        }
        while(!st.empty()) st.pop_back();
    }

    for(int j=1;j<=n;j++){
        int cnt=0;
        bool sta=1-mp[1][j];

        for(int i=1;i<=n;i++){
            if(mp[i][j]) sta=0,cnt++;
            if(!sta && !mp[i][j]){
                while(!st.empty()){
                    edge[st.back()][j].push_back({i,j,cnt*cnt});
                    st.pop_back();
                }
                sta=1,cnt=0;
            }

            if(sta) st.push_back(i);
        }
        while(!st.empty()) st.pop_back();
    }

    for(int j=1;j<=n;j++){
        int cnt=0;
        bool sta=1-mp[n][j];

        for(int i=n;i>=1;i--){
            if(mp[i][j]) sta=0,cnt++;
            if(!sta && !mp[i][j]){
                while(!st.empty()){
                    edge[st.back()][j].push_back({i,j,cnt*cnt});
                    st.pop_back();
                }
                sta=1,cnt=0;
            }

            if(sta) st.push_back(i);
        }
        while(!st.empty()) st.pop_back();
    }

    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;
}

Compilation message (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:122:12: warning: 'sy' may be used uninitialized in this function [-Wmaybe-uninitialized]
     pq.push({sx,sy,0});
     ~~~~~~~^~~~~~~~~~~
aqua.cpp:130:19: warning: 'ex' may be used uninitialized in this function [-Wmaybe-uninitialized]
             printf("%lld",dist[ex][ey]);
             ~~~~~~^~~~~~~~~~~~~~~~~~~~~
aqua.cpp:130:19: warning: 'ey' may be used uninitialized in this function [-Wmaybe-uninitialized]
aqua.cpp:122:12: warning: 'sx' may be used uninitialized in this function [-Wmaybe-uninitialized]
     pq.push({sx,sy,0});
     ~~~~~~~^~~~~~~~~~~

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