5437 | 2023. 06. 01 14:33:53 | Timi | Fantasztikus Kaland Nyílországban | cpp14 | Hibás válasz 0/100 | 41ms | 68228 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)-1;
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/10 | ||||||
1 | Hibás válasz | 3ms | 2808 KiB | ||||
2 | Hibás válasz | 3ms | 2996 KiB | ||||
3 | Hibás válasz | 3ms | 3120 KiB | ||||
4 | Hibás válasz | 3ms | 3364 KiB | ||||
5 | Hibás válasz | 3ms | 3532 KiB | ||||
6 | Hibás válasz | 3ms | 3808 KiB | ||||
7 | Hibás válasz | 3ms | 3984 KiB | ||||
8 | Hibás válasz | 3ms | 4252 KiB | ||||
9 | Hibás válasz | 3ms | 4508 KiB | ||||
10 | Hibás válasz | 3ms | 4632 KiB | ||||
subtask2 | 0/12 | ||||||
1 | Hibás válasz | 3ms | 4856 KiB | ||||
2 | Hibás válasz | 3ms | 5104 KiB | ||||
3 | Hibás válasz | 3ms | 5208 KiB | ||||
4 | Hibás válasz | 3ms | 5152 KiB | ||||
5 | Hibás válasz | 3ms | 5196 KiB | ||||
6 | Hibás válasz | 3ms | 5224 KiB | ||||
7 | Hibás válasz | 3ms | 5364 KiB | ||||
8 | Hibás válasz | 3ms | 5544 KiB | ||||
9 | Hibás válasz | 3ms | 5660 KiB | ||||
10 | Hibás válasz | 3ms | 5700 KiB | ||||
subtask3 | 0/12 | ||||||
1 | Hibás válasz | 3ms | 5636 KiB | ||||
2 | Hibás válasz | 3ms | 5644 KiB | ||||
3 | Hibás válasz | 3ms | 5640 KiB | ||||
4 | Hibás válasz | 3ms | 5636 KiB | ||||
subtask4 | 0/16 | ||||||
1 | Hibás válasz | 3ms | 5636 KiB | ||||
2 | Hibás válasz | 3ms | 5656 KiB | ||||
3 | Hibás válasz | 3ms | 5692 KiB | ||||
4 | Hibás válasz | 3ms | 5716 KiB | ||||
5 | Hibás válasz | 3ms | 5860 KiB | ||||
6 | Hibás válasz | 3ms | 5848 KiB | ||||
7 | Hibás válasz | 3ms | 5796 KiB | ||||
8 | Hibás válasz | 3ms | 5772 KiB | ||||
9 | Hibás válasz | 3ms | 5772 KiB | ||||
10 | Hibás válasz | 3ms | 5764 KiB | ||||
subtask5 | 0/50 | ||||||
1 | Hibás válasz | 6ms | 8836 KiB | ||||
2 | Hibás válasz | 3ms | 7388 KiB | ||||
3 | Hibás válasz | 6ms | 9196 KiB | ||||
4 | Hibás válasz | 8ms | 10980 KiB | ||||
5 | Hibás válasz | 35ms | 39564 KiB | ||||
6 | Hibás válasz | 35ms | 39524 KiB | ||||
7 | Hibás válasz | 8ms | 22656 KiB | ||||
8 | Hibás válasz | 35ms | 39884 KiB | ||||
9 | Hibás válasz | 41ms | 68228 KiB | ||||
10 | Hibás válasz | 34ms | 54024 KiB |