Submission #1090457

#TimeUsernameProblemLanguageResultExecution timeMemory
1090457KasymKAwesome Arrowland Adventure (eJOI19_adventure)C++17
0 / 100
1 ms444 KiB
#include "bits/stdc++.h" using namespace std; #define ff first #define ss second #define all(v) v.begin(), v.end() #define ll long long #define pb push_back #define pii pair<int, int> #define pli pair<ll, int> #define pll pair<ll, ll> #define tr(i, c) for(auto i = c.begin(); i != c.end(); ++i) #define wr puts("----------------") template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;} template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;} const int N = 5e3+5; const int INF = 1e9; char c[N][N]; int dis[N][N]; int main(){ int n, m; scanf("%d%d", &n, &m); for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) scanf(" %c", &c[i][j]), dis[i][j] = INF; auto check = [&](int x, int y){ return (x >= 1 and x <= n and y >= 1 and y <= m); }; using node = tuple<int, int, int>; priority_queue<node, vector<node>, greater<node>> q; q.push({0, 1, 1}); dis[1][1] = 0; while(!q.empty()){ int x, y, step; tie(step, x, y) = q.top(); q.pop(); if(c[x][y] == 'X') continue; if(check(x, y+1)){ int add = 0; if(c[x][y] == 'N') add++; else if(c[x][y] == 'W') add += 2; else if(c[x][y] == 'S') add += 3; if(umin(dis[x][1+y], dis[x][y]+add)) q.push({dis[x][1+y], x, 1+y}); } if(check(x, y-1)){ int add = 0; if(c[x][y] == 'S') add++; else if(c[x][y] == 'E') add += 2; else if(c[x][y] == 'N') add += 3; if(umin(dis[x][y-1], dis[x][y]+add)) q.push({dis[x][y-1], x, y-1}); } if(check(x-1, y)){ int add = 0; if(c[x][y] == 'W') add++; else if(c[x][y] == 'S') add += 2; else if(c[x][y] == 'E') add += 3; if(umin(dis[x-1][y], dis[x][y]+add)) q.push({dis[x-1][y], x-1, y}); } if(check(x+1, y)){ int add = 0; if(c[x][y] == 'E') add++; else if(c[x][y] == 'N') add += 2; else if(c[x][y] == 'W') add += 3; if(umin(dis[x+1][y], dis[x][y]+add)) q.push({dis[x+1][y], x+1, y}); } } int answer = dis[n][m]; printf("%d\n", answer); return 0; }

Compilation message (stderr)

adventure.cpp: In function 'int main()':
adventure.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
adventure.cpp:25:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |             scanf(" %c", &c[i][j]), dis[i][j] = INF;
      |             ~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...