Knight's Journey On A Chessboard Editorial

Practice Problem Link: Knight's Journey On A Chessboard

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

You have a chessboard of size n*n. A knight sits on the board at a position start(x, y). The knight wants to go to another cell end(x, y).

Find the minimum number of moves required to go from the start position to the end position. If this is not possible, return -1.

Approach

Make a matrix of size n * n and initialize every cell to -1. Now initialize the start cell to 0 and perform a BFS from the start cell by trying all the 8 positions where the knight can move from its current position to get the shortest path to the end position.

Analysis

• Time Complexity: O(n2)
• Auxiliary Space Complexity: O(n2)

Implementation

C++

/* This is the Cell class definition
class Cell {
public:
    int x, y;
    Cell(int x, int y) {
        this->x = x;
        this->y = y;
    }
};
*/

int minMovesRequired(int n, Cell start, Cell end) {
	vector<vector<int>> shortestPath(n + 1, vector<int> (n + 1, - 1));
	queue<pair<int, int>> reachableBlocks;
	reachableBlocks.push({start.x, start.y});
	shortestPath[start.x][start.y] = 0;
	while(!reachableBlocks.empty()) {
		pair<int, int> currBlock = reachableBlocks.front();
		int x = currBlock.first;
		int y = currBlock.second;
		reachableBlocks.pop();
		for (int i = max(1, x - 2); i <= min(n, x + 2); i++) {
			for (int j = max(1, y - 2); j <= min(n, y + 2); j++) {
				if(abs(x - i) + abs(y - j) == 3 && x != i && y != j && shortestPath[i][j] == - 1) {
					shortestPath[i][j] = shortestPath[x][y] + 1;
					reachableBlocks.push({i, j});
				}
			}
		}
	}
	return shortestPath[end.x][end.y];
}

Java

/* This is the Cell class definition
class Cell {
	public int x, y;
    public Cell(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
*/

class Solution {
	class Pair {
		int first, second;
		Pair (int x, int y) {
			first = x;
			second = y;
		}
	}
	int minMovesRequired(int n, Cell start, Cell end) {
    	int[][] shortestPath = new int[n + 1][n + 1];
		for (int i = 0; i <= n; i++) {
			for (int j = 0; j <= n; j++) {
				shortestPath[i][j] = - 1;
			}
		}
		Queue<Pair> reachableBlocks = new LinkedList<Pair> ();
		reachableBlocks.add(new Pair(start.x, start.y));
		shortestPath[start.x][start.y] = 0;
		while(!reachableBlocks.isEmpty()) {
			Pair currBlock = reachableBlocks.poll();
			int x = currBlock.first;
			int y = currBlock.second;
			for (int i = Math.max(1, x - 2); i <= Math.min(n, x + 2); i++) {
				for (int j = Math.max(1, y - 2); j <= Math.min(n, y + 2); j++) {
					if(Math.abs(x - i) + Math.abs(y - j) == 3 && x != i && y != j && shortestPath[i][j] == - 1) {
						shortestPath[i][j] = shortestPath[x][y] + 1;
						reachableBlocks.add(new Pair(i, j));
					}
				}
			}
		}
		return shortestPath[end.x][end.y];
	}
}