5439 | 2023. 06. 01 21:03:13 | Timi | Fantasztikus Kaland Nyílországban | cpp14 | Hibás válasz 0/100 | 35ms | 68336 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+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+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<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+3<minimum)
{
minimum=md+3;
ok=true;
}
}
if (ok)
return minimum;
else
return -1;
}
if (a[x][y]=='N')
{
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 (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+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<minimum)
{
minimum=md;
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+3<minimum)
{
minimum=md+3;
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+1<minimum)
{
minimum=md+1;
ok=true;
}
}
if (ok)
return minimum;
else
return -1;
}
if (a[x][y]=='S')
{
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<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+3<minimum)
{
minimum=md+3;
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 (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';
int b=szamol(0, 0, n, m, a, meglatogatott);
if (b==-1)
cout<<b;
else
cout<<b-1;
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/10 | ||||||
1 | Elfogadva | 3ms | 2680 KiB | ||||
2 | Elfogadva | 3ms | 2860 KiB | ||||
3 | Hibás válasz | 3ms | 3100 KiB | ||||
4 | Hibás válasz | 3ms | 3480 KiB | ||||
5 | Elfogadva | 3ms | 3636 KiB | ||||
6 | Hibás válasz | 3ms | 3744 KiB | ||||
7 | Elfogadva | 3ms | 3768 KiB | ||||
8 | Elfogadva | 3ms | 3864 KiB | ||||
9 | Elfogadva | 3ms | 4100 KiB | ||||
10 | Elfogadva | 3ms | 4220 KiB | ||||
subtask2 | 0/12 | ||||||
1 | Elfogadva | 3ms | 4324 KiB | ||||
2 | Hibás válasz | 3ms | 4404 KiB | ||||
3 | Hibás válasz | 3ms | 4516 KiB | ||||
4 | Hibás válasz | 3ms | 4584 KiB | ||||
5 | Hibás válasz | 3ms | 4604 KiB | ||||
6 | Hibás válasz | 3ms | 4872 KiB | ||||
7 | Hibás válasz | 3ms | 4872 KiB | ||||
8 | Hibás válasz | 3ms | 5068 KiB | ||||
9 | Hibás válasz | 3ms | 5068 KiB | ||||
10 | Hibás válasz | 3ms | 5112 KiB | ||||
subtask3 | 0/12 | ||||||
1 | Hibás válasz | 3ms | 5124 KiB | ||||
2 | Hibás válasz | 3ms | 5396 KiB | ||||
3 | Elfogadva | 3ms | 5400 KiB | ||||
4 | Hibás válasz | 3ms | 5392 KiB | ||||
subtask4 | 0/16 | ||||||
1 | Elfogadva | 3ms | 5396 KiB | ||||
2 | Hibás válasz | 3ms | 5412 KiB | ||||
3 | Hibás válasz | 3ms | 5628 KiB | ||||
4 | Hibás válasz | 3ms | 5688 KiB | ||||
5 | Hibás válasz | 3ms | 5756 KiB | ||||
6 | Hibás válasz | 3ms | 5980 KiB | ||||
7 | Hibás válasz | 3ms | 5984 KiB | ||||
8 | Hibás válasz | 3ms | 5956 KiB | ||||
9 | Hibás válasz | 3ms | 6056 KiB | ||||
10 | Hibás válasz | 3ms | 6200 KiB | ||||
subtask5 | 0/50 | ||||||
1 | Elfogadva | 6ms | 9264 KiB | ||||
2 | Hibás válasz | 3ms | 7812 KiB | ||||
3 | Hibás válasz | 6ms | 9636 KiB | ||||
4 | Hibás válasz | 7ms | 11364 KiB | ||||
5 | Hibás válasz | 30ms | 39940 KiB | ||||
6 | Hibás válasz | 35ms | 39900 KiB | ||||
7 | Elfogadva | 8ms | 23036 KiB | ||||
8 | Hibás válasz | 34ms | 40112 KiB | ||||
9 | Hibás válasz | 35ms | 68336 KiB | ||||
10 | Hibás válasz | 35ms | 54128 KiB |