#include<bits/stdc++.h>

#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define mt make_tuple

using namespace std;

struct struk
{
    int x, y, tip, vr;
};
inline bool operator<(const struk& a, const struk& b)
{
    return a.vr > b.vr;
}

priority_queue<struk> niz;
int mat[510][510];
int vreme[510][510][6];
int obidjeni[510][510][6];

int INF = 1000000009;
int n, m;

void pred()
{
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            for(int z = 1; z <= 5; z++)
                vreme[i][j][z] = INF;
}

bool moze(int a, int b)
{
    return a >= 0 && a < n && b >= 0 && b < m && mat[a][b] == 0;
}

void update(int a, int b, int c, int vred)
{
    struk pom;
    pom.x = a;
    pom.y = b;
    pom.tip = c;
    pom.vr = vreme[a][b][c];
    vreme[a][b][c] = vred;



    if(obidjeni[a][b][c] == 0)
    {
        pom.vr = vred;
        niz.push(pom);
    }
}

void menjaj(struk pom)
{
    for(int i = 1; i <= 5; i++)
    {
        if(i == pom.tip) continue;
        int t = vreme[pom.x][pom.y][pom.tip] + i;
        if(t < vreme[pom.x][pom.y][i]) update(pom.x, pom.y, i, t);
    }
}

void pomeri(struk pom, int pi, int pj, int cnt)
{
    int i = pom.x + pi;
    int j = pom.y + pj;
    while(cnt > 0 && moze(i, j))
    {
        int t = vreme[pom.x][pom.y][pom.tip] + 1;
        if(t < vreme[i][j][pom.tip]) update(i, j, pom.tip, t);

        cnt--;
        i += pi;
        j += pj;
    }

}

void kralj(struk pom)
{
    for(int i = -1; i <= 1; i++)
    {
        for(int j = -1; j <= 1; j++)
        {
            if(i == 0 && j == 0) continue;
            pomeri(pom, i, j, 1);
        }
    }
}

void lovac(struk pom)
{
    for(int i = -1; i <= 1; i++)
    {
        for(int j = -1; j <= 1; j++)
        {
            if(i == 0 || j == 0) continue;
            pomeri(pom, i, j, 1000);
        }
    }
}

void top(struk pom)
{
    for(int i = -1; i <= 1; i++)
    {
        for(int j = -1; j <= 1; j++)
        {
            if((i != 0 && j != 0) || (i == 0 && j == 0)) continue;
            pomeri(pom, i, j, 1000);
        }
    }
}
void konj(struk pom)
{
    pomeri(pom, 2, 1, 1);
    pomeri(pom, 2, -1, 1);
    pomeri(pom, -2, 1, 1);
    pomeri(pom, -2, -1, 1);
    pomeri(pom, 1, 2, 1);
    pomeri(pom, 1, -2, 1);
    pomeri(pom, -1, 2, 1);
    pomeri(pom, -1, -2, 1);
}
void kraljica(struk pom)
{
    top(pom);
    lovac(pom);
}


void siri(struk pom)
{
    if(pom.tip == 1) kralj(pom);
    if(pom.tip == 2) lovac(pom);
    if(pom.tip == 3) top(pom);
    if(pom.tip == 4) konj(pom);
    if(pom.tip == 5) kraljica(pom);
}



int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    pred();
    for(int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        for(int j = 0; j < m; j++)
            if(s[j] == '#') mat[i][j] = 1;
            else mat[i][j] = 0;
    }

    update(0,0,1,0);

    int br = 1;
    while(niz.size() > 0)
    {
        struk pom = niz.top();
        if(obidjeni[pom.x][pom.y][pom.tip] == 0)
        {
            br++;
            obidjeni[pom.x][pom.y][pom.tip] = 1;
            menjaj(pom);
            siri(pom);
        }


        niz.pop();
    }
    int best = INF;
    for(int z = 1; z <= 5; z++) best = min(best, vreme[n-1][m-1][z]);

    if(best == INF) cout << -1;
    else cout << best;
    return 0;
}

Petlja.org
Fondacija Petlja
loop@petlja.org
© Copyright 2018. Petlja.org
Grafički dizajn enjoy.ing