Mam takie zadanie,
Zając
Limit pamięci: 32 MB
Zając Bajtek mieszka na polanie w kształcie prostokąta o wymiarach metrów n x m. Polana ta jest podzielona na pól n * m - kwadratów o boku długości 1 metra. Na niektórych polach znajdują się kopce kreta, które Bajtek zawsze omija.
Każdy skok Bajtka ma długość dokładnie pierwiastek z 5, a ponieważ Bajtek jest strasznym pedantem - zawsze chce skoczyć dokładnie na środek pola. Tak więc z pola o współrzędnych (x, y) Bajtek może skoczyć tylko na pola o współrzędnych: (x+1,y+2), (x+1,y-2), (x-1,y+2), (x-1,y-2), (x+2,y+1), (x+2,y-1), (x-2, y+1), lub (x-2,y-1), o ile nie wiąże się to z wyskoczeniem poza polanę.
Bajtek chciałby jak najszybciej dotrzeć do swojej nory, nie skacząc na pola, na których znajdują się kopce kreta. Mając dane pole, na którym stoi Bajtek, oraz pole, na którym znajduje się jego nora, pomóż mu obliczyć minimalną liczbę skoków, jakie musi wykonać, aby dotrzeć do nory.
Wejście
W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite n oraz m oddzielone pojedynczym odstępem (1 <= n,m <= 1000, n*m >= 2), oznaczające rozmiary polany. Kolejne wierszy zawiera po znaków oznaczających poszczególne pola polany:
"." oznacza wolne pole, czyli takie, na które Bajtek może wskoczyć,
"x" oznacza pole, na którym znajduje się kopiec kreta,
"z" oznacza pole, na którym obecnie stoi zając Bajtek,
"n" oznacza, że na tym polu jest nora Bajtka.
Możesz założyć, że dokładnie jedno pole polany jest oznaczone jako "z" oraz dokładnie jedno pole jest oznaczone jako "n".
Wyjście
W pierwszym i jedynym wierszu standardowego wyjścia powinna znaleźć się jedna dodatnia liczba całkowita równa minimalnej liczbie skoków, jakie Bajtek musi wykonać, aby dotrzeć do swojej nory, lub słowo "NIE", jeśli dotarcie Bajtka do nory przy użyciu poprawnych skoków nie jest możliwe.
Przykład
Dla danych wejściowych:
4 5
.zx.x
.xx..
..x.x
x..n.
poprawną odpowiedzią jest:
3
No i mam taki kod z BFS ale jest za wolny
#include <bits/stdc++.h>
using namespace std;
int count_jumps(vector<vector<bool>> & glade, pair<int, int> & start_pos, pair<int, int> & end_pos){
vector<int> dirs = {1,2, 1,-2, -1,2, -1,-2, 2,1, 2,-1, -2,1, -2,-1};
queue<pair<int, int>> que;
set<pair<int, int>> seen;
int jump_count = 0;
seen.insert(start_pos);
que.push(start_pos);
while (que.size() > 0){
int que_size = que.size();
for (int next_pos = 0; next_pos < que_size; next_pos++){
for (int i = 0; i < dirs.size(); i += 2){
pair<int, int> new_pos = make_pair(que.front().first + dirs[i], que.front().second + dirs[i+1]);
if (new_pos.first >= 0 && new_pos.first < glade.size() && new_pos.second >= 0 && new_pos.second < glade[0].size())
if (seen.count(new_pos) == 0)
if (glade[new_pos.first][new_pos.second]){
if (new_pos.first == end_pos.first && new_pos.second == end_pos.second)
return jump_count + 1;
que.push(new_pos);
seen.insert(new_pos);
}
}
que.pop();
}
jump_count++;
}
return -1;
}
void load_glade(vector<vector<bool>> & glade, pair<int, int> & start_pos, pair<int, int> & end_pos){
char ch;
for (int i = 0; i < glade.size(); i++)
for (int j = 0; j < glade[0].size(); j++){
cin >> ch;
if (ch == 'z')
start_pos = make_pair(i, j);
else if (ch == 'n' || ch == '.'){
if (ch == 'n')
end_pos = make_pair(i, j);
glade[i][j] = true;
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
int n, m, ans;
pair<int, int> start_pos, end_pos;
cin >> n >> m;
vector<vector<bool>> glade(n, vector<bool>(m));
load_glade(glade, start_pos, end_pos);
ans = count_jumps(glade, start_pos, end_pos);
if (ans == -1)
cout << "NIE";
else
cout << ans;
return 0;
}
czy jest coś nie tak z moją implementacją czy trzeba tutaj użyć czegoś sprytniejszego niż sam bfs?
LINK DO ZADANIA
TUTAJ TESTUJE