Submission #286523

#	Time	Username	Problem	Language	Result	Execution time	Memory
286523		MasterTaster	Awesome Arrowland Adventure (eJOI19_adventure)	C++14	100 / 100	253 ms	39396 KiB

adventure

#include <bits/stdc++.h>

#define INF 100000000000000000LL

using namespace std;

int tabla[550][550];
long long d[250010];
vector<int> g[250010], w[250010];
bool visited[250010];
int n, m;
string s;

void dijkstra()
{
    for (int i=0; i<n*m; i++) d[i]=-INF;
    d[0]=0;
    for (int i=0; i<n*m; i++) visited[i]=false;

    priority_queue<pair<int, int>> pq;
    pq.push({0, 0});
    while (!pq.empty())
    {
        int t=-pq.top().first; int u=pq.top().second; pq.pop();
        if (visited[u]) continue;
        d[u]=t;
        visited[u]=true;
        for (int i=0; i<g[u].size(); i++) pq.push({-t-w[u][i], g[u][i]});
    }
}
int dist(int x, int y)
{
    return (y+4-x)%4;
}

int main()
{
    cin>>n>>m;

    for (int i=0; i<n; i++)
    {
        cin>>s;
        for (int j=0; j<m; j++)
        {
            if (s[j]=='N')
                tabla[i][j]=1;
            else if (s[j]=='E')
                tabla[i][j]=2;
            else if (s[j]=='S')
                tabla[i][j]=3;
            else if (s[j]=='W')
                tabla[i][j]=4;
            else
                tabla[i][j]=-1;
        }
    }

    for (int i=0; i<n; i++)
    {
        for (int j=0; j<m; j++)
        {
            if (tabla[i][j]==-1) continue;
            int pos=i*m+j;
            if (i==0 && j==0)
            {
                g[pos].push_back(i*m+j+1);
                w[pos].push_back(dist(tabla[i][j], 2));

                g[pos].push_back((i+1)*m+j);
                w[pos].push_back(dist(tabla[i][j], 3));
            }
            else if (i==n-1 && j==m-1)
            {
                g[pos].push_back(i*m+j-1);
                w[pos].push_back(dist(tabla[i][j], 4));

                g[pos].push_back((i-1)*m+j);
                w[pos].push_back(dist(tabla[i][j], 1));
            }
            else if (i==0 && j==m-1)
            {
                g[pos].push_back(i*n+j-1);
                w[pos].push_back(dist(tabla[i][j], 4));

                g[pos].push_back((i+1)*m+j);
                w[pos].push_back(dist(tabla[i][j], 3));
            }
            else if (j==0 && i==n-1)
            {
                g[pos].push_back(i*m+j+1);
                w[pos].push_back(dist(tabla[i][j], 2));

                g[pos].push_back((i-1)*m+j);
                w[pos].push_back(dist(tabla[i][j], 1));
            }
            else if (i==0)
            {
                g[pos].push_back(i*m+j+1);
                w[pos].push_back(dist(tabla[i][j], 2));

                g[pos].push_back(i*m+j-1);
                w[pos].push_back(dist(tabla[i][j], 4));

                g[pos].push_back((i+1)*m+j);
                w[pos].push_back(dist(tabla[i][j], 3));
            }
            else if (j==0)
            {
                g[pos].push_back(i*m+j+1);
                w[pos].push_back(dist(tabla[i][j], 2));

                g[pos].push_back((i-1)*m+j);
                w[pos].push_back(dist(tabla[i][j], 1));

                g[pos].push_back((i+1)*m+j);
                w[pos].push_back(dist(tabla[i][j], 3));
            }
            else if (i==n-1)
            {
                g[pos].push_back(i*m+j+1);
                w[pos].push_back(dist(tabla[i][j], 2));

                g[pos].push_back(i*m+j-1);
                w[pos].push_back(dist(tabla[i][j], 4));

                g[pos].push_back((i-1)*m+j);
                w[pos].push_back(dist(tabla[i][j], 1));
            }
            else if (j==m-1)
            {
                g[pos].push_back(i*m+j-1);
                w[pos].push_back(dist(tabla[i][j], 4));

                g[pos].push_back((i-1)*m+j);
                w[pos].push_back(dist(tabla[i][j], 1));

                g[pos].push_back((i+1)*m+j);
                w[pos].push_back(dist(tabla[i][j], 3));
            }
            else
            {
                g[pos].push_back(i*m+j-1);
                w[pos].push_back(dist(tabla[i][j], 4));

                g[pos].push_back(i*m+j+1);
                w[pos].push_back(dist(tabla[i][j], 2));

                g[pos].push_back((i-1)*m+j);
                w[pos].push_back(dist(tabla[i][j], 1));

                g[pos].push_back((i+1)*m+j);
                w[pos].push_back(dist(tabla[i][j], 3));
            }
        }
    }

    dijkstra();

    /*for (int i=0; i<n; i++)
    {
        for (int j=0; j<m; j++)
            cout<<d[m*i+j]<<" ";
        cout<<endl;
    }*/

    if (d[n*m-1]==-INF) cout<<-1;
    else cout<<d[n*m-1];
}



/// FAKESOLVE
/*for (int i=0; i<549; i++)
    {
        for (int j=0; j<549; j++) dp[i][j]=INF;
    }

    cin>>n>>m;

    for (int i=0; i<n; i++)
    {
        string s;
        cin>>s;
        for (int j=0; j<m; j++)
        {
            if (s[j]=='N')
                matra[i][j]=0;
            else if (s[j]=='E')
                matra[i][j]=1;
            else if (s[j]=='S')
                matra[i][j]=2;
            else if (s[j]=='W')
                matra[i][j]=3;
            else
                matra[i][j]=-1;
        }
    }

    for (int i=0; i<n; i++)
    {
        for (int j=0; j<m; j++)
        {
            if (i==0 && j==0) dp[i][j]=0;
            else if (i==0)
            {
                if (matra[i][j-1]==-1) dp[i][j]=INF;
                else dp[i][j]=dp[i][j-1]+(5-matra[i][j-1])%4;
            }
            else if (j==0)
            {
                if (matra[i-1][j]==-1) dp[i][j]=INF;
                else dp[i][j]=dp[i-1][j]+(6-matra[i-1][j])%4;
            }
            else
            {
                if (matra[i-1][j]==-1) dp[i][j]=INF;
                else dp[i][j]=dp[i-1][j]+(6-matra[i-1][j])%4;

                if (matra[i][j-1]!=-1) dp[i][j]=min(dp[i][j], dp[i][j-1]+(6-matra[i][j-1])%4);
            }
        }
    }

    for (int i=0; i<n; i++)
    {
        for (int j=0; j<m; j++)
            cout<<dp
    }

    cout<<dp[n-1][m-1];*/

Compilation message (stderr)

adventure.cpp: In function 'void dijkstra()':
adventure.cpp:28:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for (int i=0; i<g[u].size(); i++) pq.push({-t-w[u][i], g[u][i]});
      |                       ~^~~~~~~~~~~~

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