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 |