oj.uz

답안 #446790

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
446790 2021-07-23T09:17:15 Z BT21tata Awesome Arrowland Adventure (eJOI19_adventure) C++17
0 / 100
 6 ms 7244 KB 
#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]<<' ';*/
    cout<<dis[n][m]<<endl;
    return 0;
}
/*
    N - 0 - up
    E - 1 - right →
    S - 2 - down
    W - 3 - left ←

*/

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 7244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 7244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 7244 KB Output is correct
2 Correct 5 ms 7244 KB Output is correct
3 Incorrect 6 ms 7244 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 7244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 7244 KB Output isn't correct
2 Halted 0 ms 0 KB -