Submission #373220

#	Time	Username	Problem	Language	Result	Execution time	Memory
373220		kkk	Awesome Arrowland Adventure (eJOI19_adventure)	C++14	0 / 100	68 ms	102404 KiB

adventure

#include<string>
#include<vector>
#include<iostream>
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
queue<int>v[300000];
char a[300002];
int used[300000];
long long dist[300002];
int main()
{
    /*ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);*/
    long long n,m,i,j,bru=1,brx=0;
    cin>>n>>m;
    char c;
    for(i=1; i<=n*m; i++)
    {
        cin>>a[i];
        if(a[i]=='X')
            brx++;
        dist[i]=999999999;
    }
    v[0].push(1);
    int is=0;
    for(i=0; is<2; i++)
    {
        while(!v[i].empty())
        {
            int t=v[i].front();
            v[i].pop();
            if(t<=0 || t>=n*m)
            if(is==2)
                break;
            if(t==n*m)
                is++;
            if(!used[t])
                bru++;
            used[t]++;
            if(a[t]=='X')
            {
                dist[t]=min(dist[t],i);
                continue;
            }
            if(dist[t]<=i)
                continue;
            dist[t]=min(dist[t],i);

            if(a[t]=='E')
            {
                if(t%m!=0)
                    v[i].push(t+1);
                if(t+m<=n*m)
                    v[i+1].push(t+m);
                if((t-1)%m>1&&(t-1)%m>1)
                    v[i+2].push(t-1);
                if((t-m)%m>1 &&(t-m)%m>1)
                    v[i+3].push(t-m);
            }
            if(a[t]=='W')
            {
                if(t%m!=0)
                    v[i+2].push(t+1);
                if(t+m<=n*m)
                    v[i+3].push(t+m);
                if((t-1)%m>1&&(t-1)%m>1)
                    v[i].push(t-1);
                if((t-m)%m>1 &&(t-m)%m>1)
                    v[i+1].push(t-m);
            }
            if(a[t]=='S')
            {
                if(t%m!=0)
                    v[i+3].push(t+1);
                if(t+m<=n*m)
                    v[i].push(t+m);
                if((t-1)%m>1&&(t-1)%m>1)
                    v[i+1].push(t-1);
                if((t-m)%m>1 &&(t-m)%m>1)
                    v[i+2].push(t-m);
            }
            if(a[t]=='N')
            {
                if(t%m!=0)
                    v[i+1].push(t+1);
                if(t+m<=n*m)
                    v[i+2].push(t+m);
                if((t-1)%m>1&&(t-1)%m>1)
                    v[i+3].push(t-1);
                if((t-m)%m>1 &&(t-m)%m>1)
                    v[i].push(t-m);
            }
        }
    }
    cout<<dist[n*m]<<endl;
}

Compilation message (stderr)

adventure.cpp: In function 'int main()':
adventure.cpp:16:21: warning: unused variable 'j' [-Wunused-variable]
   16 |     long long n,m,i,j,bru=1,brx=0;
      |                     ^
adventure.cpp:18:10: warning: unused variable 'c' [-Wunused-variable]
   18 |     char c;
      |          ^

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