5438 | 2023. 06. 01 14:34:26 | Timi | Fantasztikus Kaland Nyílországban | cpp14 | Hibás válasz 22/100 | 35ms | 68408 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';
cout<<szamol(0, 0, n, m, a, meglatogatott);
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
subtask1 | 10/10 | ||||||
1 | Elfogadva | 3ms | 2812 KiB | ||||
2 | Elfogadva | 3ms | 3080 KiB | ||||
3 | Elfogadva | 3ms | 3324 KiB | ||||
4 | Elfogadva | 3ms | 3556 KiB | ||||
5 | Elfogadva | 3ms | 3724 KiB | ||||
6 | Elfogadva | 3ms | 3800 KiB | ||||
7 | Elfogadva | 3ms | 3868 KiB | ||||
8 | Elfogadva | 3ms | 4120 KiB | ||||
9 | Elfogadva | 3ms | 4348 KiB | ||||
10 | Elfogadva | 3ms | 4336 KiB | ||||
subtask2 | 12/12 | ||||||
1 | Elfogadva | 3ms | 4476 KiB | ||||
2 | Elfogadva | 3ms | 4648 KiB | ||||
3 | Elfogadva | 3ms | 4840 KiB | ||||
4 | Elfogadva | 3ms | 4992 KiB | ||||
5 | Elfogadva | 3ms | 5176 KiB | ||||
6 | Elfogadva | 3ms | 5204 KiB | ||||
7 | Elfogadva | 3ms | 5220 KiB | ||||
8 | Elfogadva | 3ms | 5184 KiB | ||||
9 | Elfogadva | 3ms | 5192 KiB | ||||
10 | Elfogadva | 3ms | 5388 KiB | ||||
subtask3 | 0/12 | ||||||
1 | Elfogadva | 3ms | 5324 KiB | ||||
2 | Hibás válasz | 3ms | 5324 KiB | ||||
3 | Elfogadva | 3ms | 5328 KiB | ||||
4 | Hibás válasz | 3ms | 5456 KiB | ||||
subtask4 | 0/16 | ||||||
1 | Elfogadva | 3ms | 5456 KiB | ||||
2 | Hibás válasz | 3ms | 5572 KiB | ||||
3 | Hibás válasz | 3ms | 5736 KiB | ||||
4 | Hibás válasz | 3ms | 5892 KiB | ||||
5 | Hibás válasz | 3ms | 5952 KiB | ||||
6 | Hibás válasz | 3ms | 5940 KiB | ||||
7 | Hibás válasz | 3ms | 5892 KiB | ||||
8 | Hibás válasz | 3ms | 5864 KiB | ||||
9 | Hibás válasz | 3ms | 5964 KiB | ||||
10 | Hibás válasz | 3ms | 5952 KiB | ||||
subtask5 | 0/50 | ||||||
1 | Elfogadva | 6ms | 9168 KiB | ||||
2 | Hibás válasz | 3ms | 7720 KiB | ||||
3 | Hibás válasz | 6ms | 9660 KiB | ||||
4 | Hibás válasz | 8ms | 11232 KiB | ||||
5 | Hibás válasz | 35ms | 39804 KiB | ||||
6 | Hibás válasz | 32ms | 39768 KiB | ||||
7 | Elfogadva | 8ms | 22904 KiB | ||||
8 | Hibás válasz | 32ms | 39936 KiB | ||||
9 | Hibás válasz | 35ms | 68408 KiB | ||||
10 | Hibás válasz | 35ms | 54204 KiB |