Submission #1262629

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262629		iordache_	Awesome Arrowland Adventure (eJOI19_adventure)	C++20	12 / 100	8 ms	328 KiB

adventure

#include <bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;
const int N=5e2+5;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
char v[N][N];
bool vis[N][N];
bool dfs(vector<vector<int>> dir, int x=1, int y=1)
{
    if(x<1||x>3||y<1||y>3) return 0;
    if(vis[x][y]) return 0;
    vis[x][y]=1;
    if(x==3&&y==3) return 1;
    if(v[x][y]=='X') return 0;
    return dfs(dir,x+dx[dir[x][y]],y+dy[dir[x][y]]);
}
int bkt(int x, int y, int cost, vector<vector<int>> dir)
{
    //cout<<x<<" "<<y<<"  ";
    //if(x>3||y>3) return 1e18;
    if(x==4)
    {
        for(int i=1;i<=3;++i) for(int j=1;j<=3;++j) vis[i][j]=0,dir[i][j]%=4;
        /*for(int i=1;i<=3;++i)
        {
            for(int j=1;j<=3;++j) cout<<dir[i][j]<<" ";
            cout<<'\n';
        }
        cout<<'\n';*/
        if(dfs(dir)) return cost;
        return 1e18;
    }
    assert(1<=x&&x<=3&&1<=y&&y<=3);
    int nx=x,ny=y+1;
    if(ny==4) ++nx,ny=1;
    if(v[x][y]=='X') return bkt(nx,ny,cost,dir);
    int mn=1e18;
    mn=min(mn,bkt(nx,ny,cost,dir));
    ++dir[x][y];
    mn=min(mn,bkt(nx,ny,++cost,dir));
    ++dir[x][y];
    mn=min(mn,bkt(nx,ny,++cost,dir));
    ++dir[x][y];
    mn=min(mn,bkt(nx,ny,++cost,dir));
    return mn;
}
signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) cin>>v[i][j];
    vector<vector<int>> dir(4,vector<int>(4));
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j)
    {
        if(v[i][j]=='X') continue;
        if(v[i][j]=='N') dir[i][j]=0;
        if(v[i][j]=='E') dir[i][j]=1;
        if(v[i][j]=='S') dir[i][j]=2;
        if(v[i][j]=='W') dir[i][j]=3;
    }
    /*for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j) cout<<dir[i][j]<<" ";
        cout<<'\n';
    }
    cout<<'\n';*/
    //return 0;
    int ans=bkt(1,1,0,dir);
    cout<<(ans==1e18 ? -1:ans);
}

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