제출 #736908

#제출 시각아이디문제언어결과실행 시간메모리
736908ksu2009enAwesome Arrowland Adventure (eJOI19_adventure)C++14
50 / 100
2037 ms1136 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 int 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; void count_dp(ll &r, ll &c, ll step){ if(r < 1 || c < 1 || r > n || c > m || dp[r][c] <= step){ return; } if(a[r][c] == 'X'){ if(r == n && c == m) dp[r][c] = step; return; } dp[r][c] = step; char v = a[r][c]; for(int i = 0; i < 4; i++){ auto y = move(r, c, v); count_dp(y.first, y.second, step + i); v = rotate(v); } } ll cost(char a, char b){ for(int i = 0; i < 4; i++){ if(a == b) return i; a = rotate(a); } return 0; } int main(){ cin >> n >> m; for(int i = 1; i <= n; i++){ cin >> a[i]; a[i] = "#" + a[i]; } for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) dp[i][j] = 1e9; ll s1 = 1; count_dp(s1, s1, 0); if(dp[n][m] == (ll)(1e9)) dp[n][m] = -1; cout << dp[n][m] << endl; return 0; } /* 2 13 SSNWNEWESEWWE WSENESSWNNSWW */ /* 2 11 W W W E S N N S S E W W E E N W W E S S W W */ /* 2 5 EXNWS SEEXX */ /* 2 4 EWEW EWXX */ /* 2 4 EWEW EWEX */
#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...