Submission #736878

#TimeUsernameProblemLanguageResultExecution timeMemory
736878ksu2009enAwesome Arrowland Adventure (eJOI19_adventure)C++14
Compilation error
0 ms0 KiB
#include <iostream> #include <vector> #include <string> #include <math.h> #include <cmath> #include <iomanip> #include <cstdio> #include <algorithm> #include <numeric> #include <map> #include <set> #include <queue> #include <stack> #include <deque> #include <bitset> #include <cstring> #include <unordered_map> using namespace std; typedef long long ll; ll dp[507][507]; string a[507]; char rotate(char c){ if(c == 'N') return 'E'; if(c == 'E') return 'S'; if(c == 'S') return 'W'; return 'N'; } pair<ll, ll> move(ll r, ll c, char v){ if(v == 'N') return {r - 1, c}; if(v == 'E') return {r, c + 1}; if(v == 'S') return {r + 1, c}; return {r, c - 1}; } ll n, m; ll count_dp(ll r, ll c){ if(r < 1 || c < 1 || r > n || c > m || dp[r][c] == -2 || (a[r][c] == 'X' && (r != n || c != m))){ // cycle return -1; } if(r == n && c == m){ return dp[r][c] = 0; } if(dp[r][c] != -1) return dp[r][c]; ll mn = 1e18; dp[r][c] = -2; char v = a[r][c]; ll can = 0; for(int i = 0; i < 4; i++){ auto y = move(r, c, v); ll cnt = count_dp(y.first, y.second); if(cnt != -1){ mn = min(mn, i + cnt); can++; } v = rotate(v); } if(can == 0){ mn = -1; return dp[r][c] = mn; } dp[r][c] = mn; for(int i = 0; i < 4; i++){ auto y = move(r, c, v); ll cnt = count_dp(y.first, y.second); v = rotate(v); } return dp[r][c] = mn; } ll cost(char a, char b){ for(int i = 0; i < 4; i++){ if(a == b) return i; a = rotate(a); } return 0; } ll n2(){ vector<vector<ll>>dp2(n + 1, vector<ll>(m + 1, 1e9)); dp2[1][1] = (a[1][1] == 'X' : 1e9 ? 0); dp2[2][1] = (a[2][1] == 'X' ? 1e9 : cost(a[1][1], 'S')); for(int j = 2; j <= m; j++){ for(int i = 1; i <= n; i++){ if(a[i][j] == 'X' && (i != n || j != m)) continue; // go from left: dp2[i][j] = dp2[i][j - 1] + cost(a[i][j - 1], 'E'); ll cnt = 0; if(i == 0){ // go from (i + 1, j) cnt = dp2[i + 1][j - 1] + cost(a[i + 1][j - 1], 'E') + cost(a[i + 1][j], 'N'); } else{ cnt = dp2[i - 1][j - 1] + cost(a[i - 1][j - 1], 'E') + cost(a[i - 1][j], 'S'); } dp2[i][j] = min(dp2[i][j], cnt); } } if(dp2[n][m] > 1e9) dp2[n][m] = -1; return dp2[n][m]; } int main(){ cin >> n >> m; for(int i = 1; i <= n; i++){ cin >> a[i]; a[i] = "#" + a[i]; } if(n == 2){ cout << n2() << endl; return 0; } for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) dp[i][j] = -1; count_dp(1, 1); if(dp[1][1] == (ll)(1e18) || dp[1][1] == -2) dp[1][1] = -1; cout << dp[1][1] << endl; return 0; } /* 2 5 ESNWX SNXEX */ /* 2 4 EWEW EWXX */ /* 2 4 EWEW EWEX */

Compilation message (stderr)

adventure.cpp: In function 'll count_dp(ll, ll)':
adventure.cpp:84:12: warning: unused variable 'cnt' [-Wunused-variable]
   84 |         ll cnt = count_dp(y.first, y.second);
      |            ^~~
adventure.cpp: In function 'll n2()':
adventure.cpp:105:32: error: expected ')' before ':' token
  105 |     dp2[1][1] = (a[1][1] == 'X' : 1e9 ? 0);
      |                 ~              ^~
      |                                )