5440 2023. 06. 01 21:36:39 Timi Fantasztikus Kaland Nyílországban cpp14 Hibás válasz 22/100 46ms 75840 KiB
#include <iostream>

using namespace std;
const int N=500;
const int M=500;
bool Matrixban(int x, int y, int n, int m)
{
    return (x>=0 && x<n && y>=0 && y<m);
}

int szamol(int x, int y, int n, int m, char a[N][M], bool meglatogatott[N][M])
{
    meglatogatott[x][y]=true;
    if (x==n-1 && y==m-1)
        return 0;
    int md, minimum=100000000;
    bool ok=false;
    if (a[x][y]=='E')
    {
        if (Matrixban(x, y+1, n, m) && a[x][y+1]!='X' && !meglatogatott[x][y+1] )
        {
             md=szamol(x, y+1, n, m, a, meglatogatott);
             if (md!=-1 && md<minimum)
             {
                minimum=md;
                ok=true;
             }
        }


        if (Matrixban(x+1, y, n, m) && a[x+1][y]!='X' && !meglatogatott[x+1][y] )
        {
             md=szamol(x+1, y, n, m, a, meglatogatott);
        if (md!=-1 && md+1<minimum)
        {
                minimum=md+1;
                ok=true;
        }
        }

        if (Matrixban(x, y-1, n, m) && a[x][y-1]!='X' && !meglatogatott[x][y-1] )
        {
             md=szamol(x, y-1, n, m, a, meglatogatott);
        if (md!=-1 && md+2<minimum)
        {
                minimum=md+2;
                ok=true;
        }
        }

        if (Matrixban(x-1, y, n, m) && a[x-1][y]!='X' && !meglatogatott[x-1][y] )
        {
             md=szamol(x-1, y, n, m, a, meglatogatott);
        if (md!=-1 && md+3<minimum)
        {
                minimum=md+3;
                ok=true;
        }
        }

        if (ok)
            return minimum;
        else
            return -1;
    }

    if (a[x][y]=='N')
    {
        if (Matrixban(x-1, y, n, m) && a[x-1][y]!='X' && !meglatogatott[x-1][y] )
        {
             md=szamol(x-1, y, n, m, a, meglatogatott);
        if (md!=-1 && md<minimum)
        {
                minimum=md;
                ok=true;
        }
        }

        if (Matrixban(x, y+1, n, m) && a[x][y+1]!='X' && !meglatogatott[x][y+1] )
        {
             md=szamol(x, y+1, n, m, a, meglatogatott);
        if (md!=-1 && md+1<minimum)
        {
                minimum=md+1;
                ok=true;
        }
        }

        if (Matrixban(x+1, y, n, m) && a[x+1][y]!='X' && !meglatogatott[x+1][y] )
        {
            md=szamol(x+1, y, n, m, a, meglatogatott);
        if (md!=-1 && md+2<minimum)
        {
                minimum=md+2;
                ok=true;
        }
        }

        if (Matrixban(x, y-1, n, m) && a[x][y-1]!='X' && !meglatogatott[x][y-1] )
        {
             md=szamol(x, y-1, n, m, a, meglatogatott);
        if (md!=-1 && md+3<minimum)
        {
                minimum=md+3;
                ok=true;
        }
        }

        if (ok)
            return minimum;
        else
            return -1;
    }

    if (a[x][y]=='W')
    {
        if (Matrixban(x, y-1, n, m) && a[x][y-1]!='X' && !meglatogatott[x][y-1] )
        {
             md=szamol(x, y-1, n, m, a, meglatogatott);
        if (md!=-1 && md<minimum)
        {
                minimum=md;
                ok=true;
        }
        }

        if (Matrixban(x-1, y, n, m) && a[x-1][y]!='X' && !meglatogatott[x-1][y] )
        {
             md=szamol(x-1, y, n, m, a, meglatogatott);
        if (md!=-1 && md+1<minimum)
        {
                minimum=md+1;
                ok=true;
        }
        }

        if (Matrixban(x, y+1, n, m) && a[x][y+1]!='X' && !meglatogatott[x][y+1] )
        {
             md=szamol(x, y+1, n, m, a, meglatogatott);
        if (md!=-1 && md+2<minimum)
        {
                minimum=md+2;
                ok=true;
        }
        }

        if (Matrixban(x+1, y, n, m) && a[x+1][y]!='X' && !meglatogatott[x+1][y] )
        {
             md=szamol(x+1, y, n, m, a, meglatogatott);
        if (md!=-1 && md+3<minimum)
        {
                minimum=md+3;
                ok=true;
        }
        }

        if (ok)
            return minimum;
        else
            return -1;
    }

    if (a[x][y]=='S')
    {
        if (Matrixban(x+1, y, n, m) && a[x+1][y]!='X' && !meglatogatott[x+1][y] )
        {
             md=szamol(x+1, y, n, m, a, meglatogatott);
        if (md!=-1 && md<minimum)
        {
                minimum=md;
                ok=true;
        }
        }

        if (Matrixban(x, y-1, n, m) && a[x][y-1]!='X' && !meglatogatott[x][y-1] )
        {
             md=szamol(x, y-1, n, m, a, meglatogatott);
        if (md!=-1 && md+1<minimum)
        {
                minimum=md+1;
                ok=true;
        }
        }

        if (Matrixban(x-1, y, n, m) && a[x-1][y]!='X' && !meglatogatott[x-1][y] )
        {
             md=szamol(x-1, y, n, m, a, meglatogatott);
        if (md!=-1 && md+2<minimum)
        {
                minimum=md+2;
                ok=true;
        }
        }

        if (Matrixban(x, y+1, n, m) && a[x][y+1]!='X' && !meglatogatott[x][y+1] )
        {
             md=szamol(x, y+1, n, m, a, meglatogatott);
        if (md!=-1 && md+3<minimum)
        {
                minimum=md+3;
                ok=true;
        }
        }

        if (ok)
            return minimum;
        else
            return -1;
    }
}
int main()
{
    int m, n, i, j;
    cin>>n>>m;
    char a[N][M];
    string x;
    bool meglatogatott[N][M];
    for (i=0; i<n; i++)
    {

        cin>>x;
        for (j=0; j<m; j++)
        {
            a[i][j]=x[j];
            meglatogatott[i][j]=false;
        }

    }
    a[n-1][m-1]='A';
    cout<<szamol(0, 0, n, m, a, meglatogatott);

    return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 10/10
1 Elfogadva 3ms 3072 KiB
2 Elfogadva 3ms 3140 KiB
3 Elfogadva 3ms 3444 KiB
4 Elfogadva 3ms 3644 KiB
5 Elfogadva 3ms 3592 KiB
6 Elfogadva 3ms 3612 KiB
7 Elfogadva 3ms 3584 KiB
8 Elfogadva 3ms 3632 KiB
9 Elfogadva 3ms 3740 KiB
10 Elfogadva 3ms 3872 KiB
subtask2 12/12
1 Elfogadva 3ms 4056 KiB
2 Elfogadva 3ms 4376 KiB
3 Elfogadva 3ms 4740 KiB
4 Elfogadva 3ms 4672 KiB
5 Elfogadva 3ms 4860 KiB
6 Elfogadva 3ms 5016 KiB
7 Elfogadva 3ms 5088 KiB
8 Elfogadva 3ms 5056 KiB
9 Elfogadva 3ms 5280 KiB
10 Elfogadva 3ms 5404 KiB
subtask3 0/12
1 Elfogadva 3ms 5332 KiB
2 Elfogadva 3ms 5336 KiB
3 Elfogadva 3ms 5472 KiB
4 Hibás válasz 3ms 5468 KiB
subtask4 0/16
1 Elfogadva 3ms 5468 KiB
2 Hibás válasz 3ms 5480 KiB
3 Hibás válasz 3ms 5532 KiB
4 Hibás válasz 3ms 5740 KiB
5 Hibás válasz 3ms 5856 KiB
6 Hibás válasz 3ms 5840 KiB
7 Hibás válasz 3ms 5808 KiB
8 Hibás válasz 3ms 5788 KiB
9 Hibás válasz 3ms 5796 KiB
10 Hibás válasz 3ms 5792 KiB
subtask5 0/50
1 Elfogadva 4ms 7428 KiB
2 Hibás válasz 3ms 6636 KiB
3 Hibás válasz 6ms 8404 KiB
4 Hibás válasz 8ms 10272 KiB
5 Hibás válasz 29ms 32824 KiB
6 Hibás válasz 32ms 32312 KiB
7 Elfogadva 8ms 19372 KiB
8 Hibás válasz 29ms 32936 KiB
9 Elfogadva 46ms 75840 KiB
10 Hibás válasz 32ms 54232 KiB