제출 #446793

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
446793		BT21tata	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	100 / 100	135 ms	26448 KiB

adventure

#include<bits/stdc++.h>
// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
typedef long long ll;
typedef long double ld;
#define SPEED ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0)
#define rall(v) (v).rbegin(),(v).rend()
#define all(v) (v).begin(),(v).end()
#define OK cerr<<"OK"<<endl<<flush
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define F first
#define S second
#define y0 jahdakdh
#define y1 jahsadakdakdh
#define endl '\n'
using namespace std;
const ll MOD=1e9+7;
// mt19937 rng(std::chrono::system_clock::now().time_since_epoch().count());

int n, m, r[4][4]={ {0,1,2,3},{3,0,1,2},{2,3,0,1},{1,2,3,0} }, dis[505][505];
char a[505][505];
vector<pair<pii, int> > g[505][505];
map<char, int>c;
bool used[505][505];
priority_queue<pair<int, pii> >q; 

int main()
{
    SPEED;
    cin>>n>>m;
    
    c['N']=0; c['E']=1; c['S']=2; c['W']=3;
    
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            cin>>a[i][j];
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
        {
            if(a[i][j]=='X') continue;
            if(i+1<=n) g[i][j].pb({{i+1, j}, r[c[a[i][j]]][2]});
            if(j+1<=m) g[i][j].pb({{i, j+1}, r[c[a[i][j]]][1]});
            if(i-1>=1) g[i][j].pb({{i-1, j}, r[c[a[i][j]]][0]});
            if(j-1>=1) g[i][j].pb({{i, j-1}, r[c[a[i][j]]][3]});
        }

    memset(dis, 63, sizeof(dis));
    dis[1][1]=0; q.push({0, {1, 1}});
    while(!q.empty())
    {
        int x=q.top().S.F, y=q.top().S.S; q.pop();
        if(used[x][y]) continue;
        used[x][y]=1;
        for(pair<pii, int> u : g[x][y])
        {
            if(dis[x][y]+u.S<dis[u.F.F][u.F.S])
            {
                dis[u.F.F][u.F.S]=dis[x][y]+u.S;
                q.push({-dis[u.F.F][u.F.S], {u.F.F, u.F.S}});
            }
        }
    }/*
    for(int i=1; i<=n; i++, cout<<endl)
        for(int j=1; j<=m; j++)
            cout<<dis[i][j]<<' ';*/
    if(dis[n][m]==1061109567) cout<<-1<<endl;
    else cout<<dis[n][m]<<endl;
    return 0;
}
/*
    N - 0 - up
    E - 1 - right →
    S - 2 - down
    W - 3 - left ←

*/

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