CareerCup

I feel like it is like a bfs problem, but I am not sure whether it satisfies interviewer? start from the origin point, and bfs search its surrounding area. Any other idea?

# Randomly assuming that target is calculated (once reached) as target = target[x]* 7, target[y]* 7 
def move(start, target):
	queue = collections.deque([[start]])
	seen = {start}
	while queue:
		path = queue.popLeft()
		x, y = path[-1]
		if x, y == target:
			return move((x, y), (target[0] * 7, target[1] * 7))
		candidates = {(x + 1, y + 1), (x - 1, y + 1), (x - 1, y - 1), (x + 1, y - 1)}
		forbidden_l = get_forbidden_cells()
		for can in candidates:
			if can not in forbidden_l  and can not in seen:
				queue.append(path + [can])
				seen.add(can)
		


def get_forbidden_cells():
	# not relevant, probably O(1)

ID DFS + BFS

to reach any row or col the minimum jumps required is row/col number/2. then need to check which is the target cell. Worst case is 3 extra jumps to reach that cell. we use this formula

A* Search should accomplish this! Use the manhattan distance from ur current space to the goal (x, y) as your heuristic.

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <utility>
// #include <abs>

using std::abs;
using std::make_pair;
using std::pair;
using std::queue;
using std::set;
using std::vector;

int minStepsToTarget(int x, int y, const set<pair<int, int>>& forbidden) {
    // Normalizing x, y to handle symmetry; a knight's move is symmetric across axes.
    x = abs(x);
    y = abs(y);
    if (x < y) std::swap(x, y);

    // Directions a knight can move.
    vector<pair<int, int>> directions = {
        {2, 1}, {1, 2}, {-1, 2}, {-2, 1},
        {-2, -1}, {-1, -2}, {1, -2}, {2, -1}
    };

    queue<pair<pair<int, int>, int>> q; // ((x, y), steps)
    set<pair<int, int>> visited; // To avoid revisiting and infinite loops.

    q.push(make_pair(make_pair(0, 0), 0)); // Start from the origin.
    visited.insert(make_pair(0, 0));

    while (!q.empty()) {
        auto front = q.front();
        q.pop();
        auto [currentX, currentY] = front.first;
        int steps = front.second;

        // Normalize the current position for symmetry.
        currentX = abs(currentX);
        currentY = abs(currentY);

        if (currentX < currentY) {
            std::swap(currentX, currentY);
        }

        // Check if we've reached the target.
        if (currentX == x && currentY == y) {
            return steps;
        }

        // Explore all possible moves.
        for (const auto& dir : directions) {
            int nextX = currentX + dir.first;
            int nextY = currentY + dir.second;
            if (nextX < nextY) {
                std::swap(nextX, nextY); // Normalize for symmetry.
            }

            // Check if the move is allowed and not yet visited.
            if (forbidden.find(make_pair(nextX, nextY)) == forbidden.end() && visited.find(make_pair(nextX, nextY)) == visited.end()) {
                q.push(make_pair(make_pair(nextX, nextY), steps + 1));
                visited.insert(make_pair(nextX, nextY));
            }
        }
    }

    // In case no path exists (shouldn't happen on an infinite board without forbidden coordinates)
    return -1;
}

int main() {
    set<pair<int, int>> forbidden = {{2, 3}, {3, 2}}; // Example forbidden coordinates.
    int x = 5, y = 5;

    std::cout << "Minimum steps to reach (" << x << ", " << y << "): " 
              << minStepsToTarget(x, y, forbidden) << std::endl;

    return 0;
}