Find the path from source to destination in a matrix that satisfies given constraints
Given an N × N matrix of positive integers, find a path from the first cell of the matrix to its last cell.
Category: Matrix
Travelling Salesman Problem using Branch and Bound
Given a set of cities and the distance between every pair of cities, the problem is to find the shortest possible route that visits every city exactly once and returns to the starting point.
Find the longest possible route in a matrix
Given a rectangular path in the form of a binary matrix, find the length of the longest possible route from source to destination by moving to only non-zero adjacent positions.
Find the shortest path in a maze
Given a maze in the form of the binary rectangular matrix, find the shortest path’s length in a maze from a given source to a given destination.
Magnet Puzzle
We are given a set of bipolar magnets, each domino-shaped. The objective is to place magnets on an M × N board, which satisfies a set of conditions where both M and N are not odd.
Print all possible Knight’s tours on a chessboard
Given a chessboard, print all sequences of moves of a knight on a chessboard such that the knight visits every square only once.
Print all possible solutions to N–Queens problem
The N–queens puzzle is the problem of placing N chess queens on an N × N chessboard so that no two queens threaten each other. Thus, the solution requires that no two queens share the same row, column, or diagonal.
Find common elements present in all rows of a matrix
Given an M × N matrix, find the common elements present in all rows of the matrix. The solution should traverse the matrix once and print the common elements in O(M × N) time.
Calculate the size of the largest plus of 1’s in a binary matrix
Given a square matrix of 0’s and 1’s, calculate the size of the largest plus formed by 1’s.
Merge `M` sorted lists each containing `N` elements
Given m sorted lists, each containing n elements, print them efficiently in sorted order.
All-Pairs Shortest Paths – Floyd Warshall Algorithm
Given a set of vertices V in a weighted graph where its edge weights w(u, v) can be negative, find the shortest path weights d(s, v) from every source s for all vertices v present in the graph. If the graph contains a negative-weight cycle, report it.
Chess Knight Problem | Find the shortest path from source to destination
Given a chessboard, find the shortest distance (minimum number of steps) taken by a knight to reach a given destination from a given source.