Submission #72392

#	Time	Username	Problem	Language	Result	Execution time	Memory
72392		BOJ 8481 (#118)	Aquatic Labyrinth (FXCUP3_aqua)	C++17	100 / 100	2538 ms	232968 KiB

aqua

#include <bits/stdc++.h>
#define dbgv(v) {for(auto x:v)cout<<x<<' ';cout<<'\n';}
#define entire(v) v.begin(),v.end()
typedef long long ll;
using namespace std;
void OJize(){
    cin.tie(NULL); ios_base::sync_with_stdio(false);
    #ifdef jh
    freopen("input.txt", "r", stdin);
    #endif
}

string grid[911];
int n=0;

int gid(int i, int j, int dir){
    // S R L D U
    return 5*(n*i+j)+dir;
}

char destruct(int v){
    int dir = v%5; v/= 5;
    int i = v/n, j = v%n;
    cout<<'('<<i<<' '<<j<<' '<<dir<<')';
    return ' ';
}

// if you want to use ll, remember to change 0x3f3f3f3f!!
const int INF = 0x3f3f3f3f;
template <typename T>
struct WGraph{
    int n; vector<vector<pair<int,T>>> adj;
    WGraph(int n): n{n}, adj{vector<vector<pair<int,T>>>(n+1)} {}
    void connect(int a, int b, T c){
        //cout<<"Connected ";
        //cout<<destruct(a);
        //cout<<destruct(b);
        //cout<<c<<'\n';
        adj[a].push_back({b,c});}
    void input(int m){
        int a,b,c;
        for(int i=0;i<m;i++){cin>>a>>b>>c; connect(a,b,c);}
    }

    T dijkstra(int v, int u){
        set<pair<T,int>> S; S.insert(make_pair(0,v));
        vector<T> dist(n+1, INF); dist[v] = 0;
        while(!S.empty()){
            int v = (*S.begin()).second, u; T c; S.erase(S.begin());
            for(auto& uc:adj[v]){
                tie(u,c) = uc;
                if(dist[u] <= dist[v]+c) continue;
                if(dist[u] != INF) S.erase(S.find({dist[u],u}));
                dist[u] = dist[v]+c; S.insert({dist[u],u});
            }
        }
        return dist[u];
    }
};

int main(){OJize();
    // Get the grid
    cin>>n;
    int si, sj, ei, ej;
    for(int i=0; i<n; i++){
        cin>>grid[i];
        for(int j=0; j<n; j++){
            if(grid[i][j] == 'M') si = i, sj = j;
            if(grid[i][j] == 'H') ei = i, ej = j;
        }
    }
    WGraph<int> G(5*n*n);
    
    // Landing
    for(int i=0; i<n; i++) for(int j=0; j<n; j++) if(grid[i][j] != 'W'){
        for(int d=1; d<=4; d++) G.connect(gid(i,j,d), gid(i,j,0), 0);
    }
    
    // Right
    int dir = 1;
    for(int i=0; i<n; i++){
        int memo1 = -1;
        int j = 0;
        while(j<n && grid[i][j] == 'W') j++;
        for(; j<n; j++){
            char prev = j==0? 'W':grid[i][j-1];
            char curr = grid[i][j];
            if(prev != 'W' && curr != 'W' && memo1 != -1) G.connect(gid(i,j,0), memo1, 0); // Same wall
            else if(prev != 'W' && curr == 'W'){
                // A new wall
                memo1 = -1;
                int j2 = j, water = 0;
                while(j2<n && grid[i][j2] == 'W') j2++, water++;
                for(; j2<n && grid[i][j2] != 'W'; j2++) G.connect(gid(i,j,dir), gid(i,j2,dir), water*water);
            }
            else if(prev == 'W' && curr != 'W'){
                // A new floor
                int j2 = j;
                while(j2<n && grid[i][j2] != 'W') j2++;
                if(j2 != n) memo1 = gid(i,j2,dir), G.connect(gid(i,j,0), memo1, 0);
            }
            else memo1 = -1;
        }
    }

    // Left
    dir = 2;
    for(int i=0; i<n; i++){
        int memo1 = -1;
        int j = n-1;
        while(j>=0 && grid[i][j] == 'W') j--;
        for(; j>=0; j--){
            char prev = j==n-1? 'W':grid[i][j+1];
            char curr = grid[i][j];
            if(prev != 'W' && curr != 'W' && memo1 != -1) G.connect(gid(i,j,0), memo1, 0); // Same wall
            else if(prev != 'W' && curr == 'W'){
                // A new wall
                memo1 = -1;
                int j2 = j, water = 0;
                while(j2>=0 && grid[i][j2] == 'W') j2--, water++;
                for(; j2>=0 && grid[i][j2] != 'W'; j2--) G.connect(gid(i,j,dir), gid(i,j2,dir), water*water);
            }
            else if(prev == 'W' && curr != 'W'){
                // A new floor
                int j2 = j;
                while(j2>=0 && grid[i][j2] != 'W') j2--;
                if(j2 != -1) memo1 = gid(i,j2,dir), G.connect(gid(i,j,0), memo1, 0);
            }
            else memo1 = -1;
        }
    }

    // Down
    dir = 3;
    for(int j=0; j<n; j++){
        int memo1 = -1;
        int i = 0;
        while(i<n && grid[i][j] == 'W') i++;
        for(; i<n; i++){
            char prev = i==0? 'W':grid[i-1][j];
            char curr = grid[i][j];
            if(prev != 'W' && curr != 'W' && memo1 != -1) G.connect(gid(i,j,0), memo1, 0); // Same wall
            else if(prev != 'W' && curr == 'W'){
                // A new wall
                memo1 = -1;
                int i2 = i, water = 0;
                while(i2<n && grid[i2][j] == 'W') i2++, water++;
                for(; i2<n && grid[i2][j] != 'W'; i2++) G.connect(gid(i,j,dir), gid(i2,j,dir), water*water);
            }
            else if(prev == 'W' && curr != 'W'){
                // A new floor
                int i2 = i;
                while(i2<n && grid[i2][j] != 'W') i2++;
                if(i2 != n) memo1 = gid(i2,j,dir), G.connect(gid(i,j,0), memo1, 0);
            }
            else memo1 = -1;
        }
    }

    // Up
    dir = 4;
    for(int j=0; j<n; j++){
        int memo1 = -1;
        int i = n-1;
        while(i>=0 && grid[i][j] == 'W') i--;
        for(; i>=0; i--){
            char prev = i==n-1? 'W':grid[i+1][j];
            char curr = grid[i][j];
            if(prev != 'W' && curr != 'W' && memo1 != -1) G.connect(gid(i,j,0), memo1, 0); // Same wall
            else if(prev != 'W' && curr == 'W'){
                // A new wall
                memo1 = -1;
                int i2 = i, water = 0;
                while(i2>=0 && grid[i2][j] == 'W') i2--, water++;
                for(; i2>=0 && grid[i2][j] != 'W'; i2--) G.connect(gid(i,j,dir), gid(i2,j,dir), water*water);
            }
            else if(prev == 'W' && curr != 'W'){
                // A new floor
                int i2 = i;
                while(i2>=0 && grid[i2][j] != 'W') i2--;
                if(i2 != -1) memo1 = gid(i2,j,dir), G.connect(gid(i,j,0), memo1, 0);
            }
            else memo1 = -1;
        }
    }

    int ans = G.dijkstra(gid(si,sj,0), gid(ei,ej,0));
    cout << (ans != INF? ans : -1);
}

Compilation message (stderr)

aqua.cpp: In function 'int main()':
aqua.cpp:18:18: warning: 'ej' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return 5*(n*i+j)+dir;
              ~~~~^~~
aqua.cpp:64:21: note: 'ej' was declared here
     int si, sj, ei, ej;
                     ^~
aqua.cpp:18:16: warning: 'ei' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return 5*(n*i+j)+dir;
               ~^~
aqua.cpp:64:17: note: 'ei' was declared here
     int si, sj, ei, ej;
                 ^~
aqua.cpp:18:18: warning: 'sj' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return 5*(n*i+j)+dir;
              ~~~~^~~
aqua.cpp:64:13: note: 'sj' was declared here
     int si, sj, ei, ej;
             ^~
aqua.cpp:18:16: warning: 'si' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return 5*(n*i+j)+dir;
               ~^~
aqua.cpp:64:9: note: 'si' was declared here
     int si, sj, ei, ej;
         ^~

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