Submission #72043

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
72043	2018-08-26T04:54:46 Z	신딩없는 신딩팀(#2212, willi19, andy627, maruii)	Aquatic Labyrinth (FXCUP3_aqua)	C++17	0 / 100	26 ms	23916 KB

aqua

#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>
#define INF 2e9
using namespace std;

struct xyw{
    int x,y,w;

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

bool mp[999][999];
int dist[999][999];

vector<xyw> edge[999][999];
priority_queue<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;
        pq.pop();

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

        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

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

Subtask #1

0 / 36.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	23676 KB	Output is correct
2	Incorrect	26 ms	23916 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2

0 / 64.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	23676 KB	Output is correct
2	Incorrect	26 ms	23916 KB	Output isn't correct
3	Halted	0 ms	0 KB	-