What is the reasoning for “if node[0] == y and node[1] == x:” in the python solution? Shouldn’t it be “node[0] == x and node[1] == y”?
This problem/section should introduce the concept of bidirectional BFS, since this would take a long time with massive values.
Works either way… but how and why…?
Should clarify that the board can go into negative coordinates.
I had put in a condition that x < 0 or y < 0 is not a valid next point. Obviously, it did not pass the tests
row=y, col=x, so get_neighbors returns (y, x) which is pushed to queue
Infinity should game board and the way the knight moves if centered at (0,0) should implying the possibility of moving in negative coordinates
Yeah, I think you are right here since the tuple is being stored as (row, col)
This is my C++ code and I don’t know why but its getting a Time Limit Exceeded for x >= 10, y >= 10
#include // cin, cout, streamsize
#include // numeric_limits
#include
#include
#include <unordered_map>
std::vector<std::vector> get_neighbours(const std::vector &node)
{
int row = node.at(0);
int col = node.at(1);
std::vector<int> delta_row {-2, -2, -1, 1, 2, 2, 1, -1};
std::vector<int> delta_col {-1, 1, 2, 2, 1, -1, -2, -2};
std::vector<std::vector<int>> result;
int neighbour_row {0};
int neighbour_col {0};
for (int i = 0; i < delta_row.size(); i++)
{
std::vector<int> co_ordinates;
neighbour_row = row + delta_row.at(i);
neighbour_col = col + delta_col.at(i);
co_ordinates.push_back(neighbour_row);
co_ordinates.push_back(neighbour_col);
result.push_back(co_ordinates);
}
return result;
}
int bfs(int x, int y)
{
int calc {0};
std::queue<std::vector> queue;
std::unordered_map<int, int> visited; // key = row, value = column
queue.push({0, 0});
visited.insert(std::make_pair(0, 0));
int moves {0};
int neighbourSize {0};
int row {0};
int col {0};
std::vector<int> node;
std::vector<std::vector<int>> neighbours;
while (!queue.empty())
{
neighbourSize = queue.size();
for (int i = 0; i < neighbourSize; i++)
{
calc++;
node = queue.front();
queue.pop();
if (node.at(0) == y && node.at(1) == x)
{
return moves;
}
neighbours = get_neighbours(node);
for (const auto &neighbour: neighbours)
{
row = neighbour.at(0);
col = neighbour.at(1);
auto it = visited.find(row);
if (it != visited.end())
{
if (it->first == row && it->second == col)
{
continue;
}
}
queue.push(neighbour);
visited[row] = col;
}
}
moves++;
}
return moves;
}
int get_knight_shortest_path(int x, int y)
{
int result = bfs(x, y);
return result;
}
void ignore_line()
{
std::cin.ignore(std::numeric_limitsstd::streamsize::max(), ‘\n’);
}
int main() {
int x;
std::cin >> x;
ignore_line();
int y;
std::cin >> y;
ignore_line();
int res = get_knight_shortest_path(x, y);
std::cout << res << ‘\n’;
}
We can impove the search if we start 2 BFS. 1 - from 0 0 and 2 - from x y.
The problem is symmetric. For any point x, y it would take the same amount of moves to reach points (-x, -y), (-x, y), (x, -y). Therefore the search can be constrained to 1 quadrant, with only two possible moves when moving from the target towards zero: (x-2, y-1) or (x-1, y-2).
This can be implemented using DFS and memoization pretty efficiently:
def minKnightMoves(self, x: int, y: int) → int:
possible_moves = lambda x, y: [[x-2, y-1], [x-1, y-2]]
memo = dict()
def dfs(x:int, y:int)->int:
x, y = abs(x), abs(y)
if (x, y) in memo:
return memo[(x,y)]
if x == 0 and y == 0:
return 0
if x+y == 2:
return 2
memo[(x, y)] = min(dfs(x-2, y-1), dfs(x-1, y-2)) + 1
return memo[(x, y)]
return dfs(x, y)
- I don’t think DFS would work on infinite graph, but correct me if I am wrong. My reaosing is that DFS would infinitely follow first path and never explore the second move option.
- yes, the outputs are the same for reflected inputs, but the moves cannot be constrained to one quadrant. (e.g. to get on square up (1, 0), you need to make 3 moves, each in different “direction”)
y is row and x is col - so that is a correct solution
“node[0] == x and node[1] == y” is incorrect but works because problem is symmetric. It takes the same amount of moves to reach (x,y) as well as (y,x)
Bi directional version
# the offsets in the eight directions
offsets = [(1, 2), (2, 1), (2, -1), (1, -2),
(-1, -2), (-2, -1), (-2, 1), (-1, 2)]
# data structures needed to move from the origin point
origin_queue = deque([(0, 0, 0)])
origin_distance = {(0, 0): 0}
# data structures needed to move from the target point
target_queue = deque([(x, y, 0)])
target_distance = {(x, y): 0}
while True:
# check if we reach the circle of target
origin_x, origin_y, origin_steps = origin_queue.popleft()
if (origin_x, origin_y) in target_distance:
return origin_steps + target_distance[(origin_x, origin_y)]
# check if we reach the circle of origin
target_x, target_y, target_steps = target_queue.popleft()
if (target_x, target_y) in origin_distance:
return target_steps + origin_distance[(target_x, target_y)]
for offset_x, offset_y in offsets:
# expand the circle of origin
next_origin_x, next_origin_y = origin_x + offset_x, origin_y + offset_y
if (next_origin_x, next_origin_y) not in origin_distance:
origin_queue.append((next_origin_x, next_origin_y, origin_steps + 1))
origin_distance[(next_origin_x, next_origin_y)] = origin_steps + 1
# expand the circle of target
next_target_x, next_target_y = target_x + offset_x, target_y + offset_y
if (next_target_x, next_target_y) not in target_distance:
target_queue.append((next_target_x, next_target_y, target_steps + 1))
target_distance[(next_target_x, next_target_y)] = target_steps + 1
I think answer for test case(3): 1,1 → 2 is incorrect. It should be 4. Please help.
Since the solution code is missing chess boundary condition (8,8).
if(x >= 0 && y >= 0 && x < m && y < n) {
neighbours.push_back(Coordinates(x, y));
}
My bad i did not consider infinite chess board.
I’m quite confused, does anybody know under which circumstances should I count the length of queue when iterating it, (and then following a for-loop pattern to iterate the length times) and which doesn’t?
They have been using the for-loop pattern for when they need to keep track of how many stages of the queue have been processed. Here you want to keep track of how many steps the knight has taken, which is sort of just a level-order traversal.
Some alternatives to the for-loop pattern for tracking the levels are enqueuing tuples as (neighbor, level+1), and maintaining a count on the grid itself.
Here they explain it a bit:
https://algo.monster/problems/binary_tree_level_order_traversal
lack of tests for most of the problems. E.g. this problem is failed for test case “2, 112”, which is caused by a missing visited check
Test case “2, 112” will output 56, it’s working. What do you mean “missing visited check”?