제출 #226613

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
226613		Theo830	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	12 / 100	6 ms	512 KiB

adventure

    #include <bits/stdc++.h>
    using namespace std;
    typedef int ll;
    ll INF = 1e9+7;
    typedef pair<ll,ll> ii;
    #define iii pair<ii,ll>
    #define f(i,a,b) for(long long i = a;i < b;i++)
    #define rf(i,a,b) for(long long i=a;i>=b;i--)
    #define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #define w(t) while(t--)
    #define c(n); cin>>n;
    #define p(n) cout<<n;
    #define pl(n) cout<<n<<"\n";
    #define ps(n); cout<<n<<" ";
    #define F first
    #define S second
    #define pb(a) push_back(a)
    #define all(x) (x).begin(), (x).end()
    #define ull unsigned long long
    #define vll vector<ll>
    #define vii vector<ii>
    #define mkp make_pair
    #define ld long double
    #define arrin(a,n) f(i,0,n){cin>>a[i];}
    #define arrout(a,n) f(i,0,n){cout<<a[i]<<" ";}
    #define prllclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
    #define PI (2LL*acos(0))
    vll visit,dist,taken;
    vector<vll> adj;
    vector<vii> adj2LL;
    priority_queue<ii,vector<ii>, greater<ii> > pq;
    void dijkstra(ll s){pq.push(ii(0,s));dist[s] = 0;while(!pq.empty()){ii f = pq.top();pq.pop();ll w = f.F;ll u = f.S;if(w > dist[u]){continue;}for(auto v:adj2LL[u]){if(dist[u] + v.S < dist[v.F]){dist[v.F] = dist[u] + v.S;pq.push(ii(dist[v.F],v.F));}}}}
    int main(void){
        fastio;
        ll n,m;
        c(n);
        c(m);
        char arr[n][m];
        f(i,0,n){
            f(j,0,m){
                c(arr[i][j]);
            }
        }
        adj2LL.assign(n*m+5,vii());
        f(i,0,n){
            f(j,0,m){
                if(arr[i][j] == 'N'){
                    if(i-1 >= 0)
                    adj2LL[j*m+i].pb(ii(j*m+i-1,0));
                    if(j+1 <= m-1)
                    adj2LL[j*m+i].pb(ii((j+1)*m+i,1));
                    if(i+1 <= n-1)
                    adj2LL[j*m+i].pb(ii(j*m+i+1,2));
                    if(j-1 >= 0)
                    adj2LL[j*m+i].pb(ii((j-1) *m + i,3));
                }
                else if(arr[i][j] == 'E'){
                    if(i-1 >= 0)
                    adj2LL[j*m+i].pb(ii(j*m+i-1,3));
                    if(j+1 <= m-1)
                    adj2LL[j*m+i].pb(ii((j+1)*m+i,0));
                    if(i+1 <= n-1)
                    adj2LL[j*m+i].pb(ii(j*m+i+1,1));
                    if(j-1 >= 0)
                    adj2LL[j*m+i].pb(ii((j-1) *m + i,2));
                }
                else if(arr[i][j] == 'S'){
                    if(i-1 >= 0)
                    adj2LL[j*m+i].pb(ii(j*m+i-1,2));
                    if(j+1 <= m-1)
                    adj2LL[j*m+i].pb(ii((j+1)*m+i,3));
                    if(i+1 <= n-1)
                    adj2LL[j*m+i].pb(ii(j*m+i+1,0));
                    if(j-1 >= 0)
                    adj2LL[j*m+i].pb(ii((j-1) *m + i,1));
                }
                else if(arr[i][j] == 'W'){
                    if(i-1 >= 0)
                    adj2LL[j*m+i].pb(ii(j*m+i-1,1));
                    if(j+1 <= m-1)
                    adj2LL[j*m+i].pb(ii((j+1)*m+i,2));
                    if(i+1 <= n-1)
                    adj2LL[j*m+i].pb(ii(j*m+i+1,3));
                    if(j-1 >= 0)
                    adj2LL[j*m+i].pb(ii((j-1) *m + i,0));
                }
            }
        }
        dist.assign(n*m+5,INF);
        dijkstra(0);
        ll i = n-1;
        ll j = m-1;
        if(dist[j*m + i] >= INF){
            pl(-1);
            return 0;
        }
        pl(dist[j*m + i]);
    }

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