Условия задачиНа стандартной шахматной доске (8х8) живут 2 шахматных коня: красный и зеленый. Обычно они беззаботно скачут по просторам доски, пощипывая шахматную травку, но сегодня особенный день: у зеленого коня день рождения. зеленый конь решил отпраздновать это событие вместе с красным. Но для осуществления этого прекрасного плана им нужно оказаться на одной клетке. Заметим, что красный и зеленый шахматные кони сильно отличаются от черного с белым: они ходят не по очереди, а одновременно, и если оказываются на одной клетке, никто никого не съедает. Сколько ходов им потребуется, чтобы насладиться праздником?
Задача заходит только на 7 тестов из 10
никак не могу понять почему
мой код
#include <bits/stdc++.h>
#include <vector>
#include <queue>
#include <limits>
#include <string>
using namespace std;
int di[8] = { -2, -2, -1, 1, 2, 2, -1, 1 };
int dj[8] = { -1, 1, -2, -2, -1, 1, 2, 2 };
int get_num(char letter) {
if (letter == 'a') {
return 1;
}
else if (letter == 'b') {
return 2;
}
else if (letter == 'c') {
return 3;
}
else if (letter == 'd') {
return 4;
}
else if (letter == 'e') {
return 5;
}
else if (letter == 'f') {
return 6;
}
else if (letter == 'g') {
return 7;
}
else{
return 8;
}
}
vector<vector<int>>d1;
void bfs1(int ui, int uj) {
queue<pair<int, int>>q;
q.push({ ui, uj });
d1[ui][uj] = 0;
while (!q.empty()) {
ui = q.front().first;
uj = q.front().second;
q.pop();
for (int h = 0; h < 8; h++) {
int toi = ui + di[h];
int toj = uj + dj[h];
if (toi < 8 && toi > -1 && toj > -1 && toj < 8) {
if (d1[toi][toj] == INT_MAX) {
d1[toi][toj] = d1[ui][uj] + 1;
q.push({ toi, toj });
}
}
}
}
}
vector<vector<int>>d2;
void bfs2(int ui, int uj) {
queue<pair<int, int>>q;
q.push({ ui, uj });
d2[ui][uj] = 0;
while (!q.empty()) {
ui = q.front().first;
uj = q.front().second;
q.pop();
for (int h = 0; h < 8; h++) {
int toi = ui + di[h];
int toj = uj + dj[h];
if (toi < 8 && toi > -1 && toj > -1 && toj < 8) {
if (d2[toi][toj] == INT_MAX) {
d2[toi][toj] = d2[ui][uj] + 1;
q.push({ toi, toj });
}
}
}
}
}
int main() {
string st, nd;
cin >> st >> nd;
int x1 = get_num(st[0]);
int y1 = st[1] - '0';
int x2 = get_num(nd[0]);
int y2 = nd[1] - '0';
d1.resize(8, vector<int>(8, INT_MAX));
bfs1(x1 - 1, y1 - 1);
d2.resize(8, vector<int>(8, INT_MAX));
bfs2(x2 - 1, y2 - 1);
int min = INT_MAX;
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
if (d2[i][j] != 0 && d1[i][j] != 0 && d1[i][j] + d2[i][j] < min) {
min = d1[i][j] + d2[i][j];
}
}
}
if (min == INT_MAX) {
cout << -1;
}
else {
cout << min / 2;
}
}
Простой
