제출 #1144885

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1144885		12345678	Awesome Arrowland Adventure (eJOI19_adventure)	C++20	100 / 100	18 ms	8516 KiB

adventure

#include <bits/stdc++.h>

using namespace std;

const int nx=505;

int n, m, dir[nx], dx[4]={-1, 0, 1, 0}, dy[4]={0, 1, 0, -1}, dp[nx][nx][4], d[nx][nx];
char mp[nx][nx];
deque<tuple<int, int, int>> dq;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    dir['N']=0, dir['E']=1, dir['S']=2, dir['W']=3;
    for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) cin>>mp[i][j], dp[i][j][0]=dp[i][j][1]=dp[i][j][2]=dp[i][j][3]=1e9, d[i][j]=dir[mp[i][j]];
    dp[1][1][d[1][1]]=0;
    dq.push_back({1, 1, d[1][1]});
    while (!dq.empty())
    {
        auto [x, y, cd]=dq.front();
        int w=dp[x][y][cd];
        dq.pop_front();
        if (mp[x][y]=='X') continue;
        int cx=x+dx[cd], cy=y+dy[cd];
        if (1<=cx&&cx<=n&&1<=cy&&cy<=m&&mp[x][y]!='X'&&dp[cx][cy][d[cx][cy]]>w) dp[cx][cy][d[cx][cy]]=w, dq.push_front({cx, cy, d[cx][cy]});
        if (dp[x][y][(cd+1)%4]>w+1) dp[x][y][(cd+1)%4]=w+1, dq.push_back({x, y, (cd+1)%4});
    }
    if (dp[n][m][d[n][m]]==1e9) cout<<-1;
    else cout<<dp[n][m][d[n][m]];
}

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