oj.uz

답안 #759707

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
759707 2023-06-16T15:40:08 Z ivaziva Awesome Arrowland Adventure (eJOI19_adventure) C++14
0 / 100
 1 ms 468 KB 
#include <bits/stdc++.h>

using namespace std;

#define MAXM 510
#define MAXN 1510

long long n;
long long m;
char matrica[MAXM][10];
vector<pair<long long,long long>> adj[MAXM];
long long dist[MAXN];

long long dikstra(long long poc)
{
    for (long long i=0;i<MAXN;i++) dist[i]=LLONG_MAX;
    dist[poc]=0;
    priority_queue<pair<long long,long long>,vector<pair<long long,long long>>,greater<pair<long long,long long>>> pq;
    pq.push({0,poc});
    while (pq.empty()==false)
    {
        long long node0=pq.top().second;
        long long dist0=pq.top().first;
        pq.pop();
        if (dist0!=dist[node0]) continue;
        long long s=adj[node0].size();
        for (long long i=0;i<s;i++)
        {
            long long node=adj[node0][i].first;
            long long distt=adj[node0][i].second;
            if (dist0+distt<dist[node])
            {
                dist[node]=distt+dist0;
                pq.push({dist[node],node});
            }
        }
    }
}

int main()
{
    cin>>n>>m;
    for (long long i=1;i<=n;i++)
    {
        for (long long j=1;j<=m;j++) cin>>matrica[i][j];
    }
    for (long long i=1;i<=n;i++)
    {
        for (long long j=1;j<=m;j++)
        {
            if (i==1)
            {
                if (j==1)
                {
                    if (matrica[i][j]=='E')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,0});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,1});
                    }
                    if (matrica[i][j]=='S')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,3});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,0});
                    }
                    if (matrica[i][j]=='W')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,2});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,3});
                    }
                    if (matrica[i][j]=='N')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,1});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,2});
                    }
                }
                else if (j==m)
                {
                    if (matrica[i][j]=='E')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,2});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,1});
                    }
                    if (matrica[i][j]=='S')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,1});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,0});
                    }
                    if (matrica[i][j]=='W')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,0});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,3});
                    }
                    if (matrica[i][j]=='N')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,3});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,2});
                    }
                }
                else
                {
                    if (matrica[i][j]=='E')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,0});
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,2});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,1});
                    }
                    if (matrica[i][j]=='S')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,3});
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,1});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,0});
                    }
                    if (matrica[i][j]=='W')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,2});
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,0});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,3});
                    }
                    if (matrica[i][j]=='N')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,1});
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,3});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,2});
                    }
                }
            }
            else if (i==n)
            {
                if (j==1)
                {
                    if (matrica[i][j]=='E')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,0});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,3});
                    }
                    if (matrica[i][j]=='S')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,3});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,2});
                    }
                    if (matrica[i][j]=='W')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,2});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,1});
                    }
                    if (matrica[i][j]=='N')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,1});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,0});
                    }
                }
                else if (j==m)
                {
                    if (matrica[i][j]=='E')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,2});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,3});
                    }
                    if (matrica[i][j]=='S')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,1});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,2});
                    }
                    if (matrica[i][j]=='W')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,0});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,1});
                    }
                    if (matrica[i][j]=='N')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,3});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,0});
                    }
                }
                else
                {
                    if (matrica[i][j]=='E')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,0});
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,2});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,3});
                    }
                    if (matrica[i][j]=='S')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,3});
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,1});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,2});
                    }
                    if (matrica[i][j]=='W')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,2});
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,0});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,1});
                    }
                    if (matrica[i][j]=='N')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,1});
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,3});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,0});
                    }
                }
            }
            else
            {
                if (j==1)
                {
                    if (matrica[i][j]=='E')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,0});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,3});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,1});
                    }
                    if (matrica[i][j]=='S')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,3});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,2});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,0});
                    }
                    if (matrica[i][j]=='W')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,2});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,1});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,3});
                    }
                    if (matrica[i][j]=='N')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,1});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,0});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,2});
                    }
                }
                else if (j==m)
                {
                    if (matrica[i][j]=='E')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,2});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,3});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,1});
                    }
                    if (matrica[i][j]=='S')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,1});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,2});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,0});
                    }
                    if (matrica[i][j]=='W')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,0});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,1});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,3});
                    }
                    if (matrica[i][j]=='N')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,3});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,0});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,2});
                    }
                }
                else
                {
                    if (matrica[i][j]=='E')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,0});
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,2});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,3});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,1});
                    }
                    if (matrica[i][j]=='S')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,3});
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,1});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,2});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,0});
                    }
                    if (matrica[i][j]=='W')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,2});
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,0});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,1});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,3});
                    }
                    if (matrica[i][j]=='N')
                    {
                        adj[(i-1)*m+j].push_back({(i-1)*m+j+1,1});
                        adj[(i-1)*m+j].push_back({(i-1)*m+j-1,3});
                        adj[(i-1)*m+j].push_back({(i-1-1)*m+j,0});
                        adj[(i-1)*m+j].push_back({(i-1+1)*m+j,2});
                    }
                }
            }
        }
    }
    dikstra(1);
    if (dist[n*m]==LLONG_MAX) cout<<-1<<endl;
    else cout<<dist[n*m]<<endl;
}

Compilation message

adventure.cpp: In function 'long long int dikstra(long long int)':
adventure.cpp:38:1: warning: no return statement in function returning non-void [-Wreturn-type]
   38 | }
      | ^

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -