Submission #959491

#	Time	Username	Problem	Language	Result	Execution time	Memory
959491		ivopav	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	100 / 100	116 ms	15872 KiB

adventure

#include <bits/stdc++.h>
using namespace std;

char slje(char str){
    if (str=='S'){
        return 'W';
    }
    if (str=='E'){
        return 'S';
    }
    if (str=='N'){
        return 'E';
    }
    if (str=='W'){
        return 'N';
    }
    
}

int kor(char str1,char str2){
    int kol=0;
    while (str1!=str2){
        kol++;
        str1=slje(str1);
    }
    return kol;
}

struct dijktyp{
    int x;
    int y;
    int dist;
};

bool operator<(dijktyp pom,dijktyp pom2){
    if (pom.dist==pom2.dist){
        if (pom.x==pom2.x){
            return pom.y<pom2.y;
        }
        return pom.x<pom2.x;
    }
    return pom.dist>pom2.dist;
}

int main(){
    int n;
    int m;
    cin >> n >> m;
    vector<vector<char>> mat={};
    for (int i=0;i<n;i++){
        mat.push_back({});
        for (int j=0;j<m;j++){
            char unos;
            cin >> unos;
            mat[i].push_back(unos);
        }
    }
    priority_queue<dijktyp> dijklis={};
    dijklis.push({0,0,0});
    vector<vector<int>> distmat=vector<vector<int>>(n,vector<int>(m,-1));
    while (dijklis.size()>0){
        dijktyp pom=dijklis.top();
        dijklis.pop();
        int x=pom.x;
        int y=pom.y;
        int dist=pom.dist;
        if (y==n-1 && x==m-1){
            cout << dist << "\n";
            exit(0);
        }
        if (distmat[y][x]!=-1 || mat[y][x]=='X'){
            continue;
        }
        //cout << x << " " << y << " " << dist << "\n";
        distmat[y][x]=dist;
        if (y>0){
            dijklis.push({x,y-1,dist+kor(mat[y][x],'N')});
        }
        if (y<n-1){
            dijklis.push({x,y+1,dist+kor(mat[y][x],'S')});
        }
        if (x>0){
            dijklis.push({x-1,y,dist+kor(mat[y][x],'W')});
        }
        if (x<m-1){
            dijklis.push({x+1,y,dist+kor(mat[y][x],'E')});
        }
    }
    cout << "-1\n";
}

Compilation message (stderr)

adventure.cpp: In function 'char slje(char)':
adventure.cpp:18:1: warning: control reaches end of non-void function [-Wreturn-type]
   18 | }
      | ^

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 16 / 16
• Subtask 5: 50 / 50