Given a chess board of dimension m * n. Find number of possible moves where knight can be moved on a chessboard from given position. If mat[i][j] = 1 then the block is filled by something else, otherwise empty. Assume that board consist of all pieces of same color, i.e., there are no blocks being attacked.
Examples:
Input : mat[][] = {{1, 0, 1, 0},
{0, 1, 1, 1},
{1, 1, 0, 1},
{0, 1, 1, 1}}
pos = (2, 2)
Output : 4
Knight can moved from (2, 2) to (0, 1), (0, 3),
(1, 0) ans (3, 0).
We can observe that knight on a chessboard moves either:
1. Two moves horizontal and one move vertical
2. Two moves vertical and one move horizontal
The idea is to store all possible moves of knight and then count number of valid moves. A move will be invalid if:
1. A block is already occupied by another piece.
2. Move is out of chessboard.
C++
// CPP program to find number of possible moves of knight #include <bits/stdc++.h> #define n 4 #define m 4 using namespace std; // To calculate possible moves int findPossibleMoves(int mat[n][m], int p, int q) { // All possible moves of a knight int X[8] = { 2, 1, -1, -2, -2, -1, 1, 2 }; int Y[8] = { 1, 2, 2, 1, -1, -2, -2, -1 }; int count = 0; // Check if each possible move is valid or not for (int i = 0; i < 8; i++) { // Position of knight after move int x = p + X[i]; int y = q + Y[i]; // count valid moves if (x >= 0 && y >= 0 && x < n && y < m && mat[x][y] == 0) count++; } // Return number of possible moves return count; } // Driver program to check findPossibleMoves() int main() { int mat[n][m] = { { 1, 0, 1, 0 }, { 0, 1, 1, 1 }, { 1, 1, 0, 1 }, { 0, 1, 1, 1 } }; int p = 2, q = 2; cout << findPossibleMoves(mat, p, q); return 0; } |
Java
// Java program to find number of possible moves of knight public class Main { public static final int n = 4; public static final int m = 4; // To calculate possible moves static int findPossibleMoves(int mat[][], int p, int q) { // All possible moves of a knight int X[] = { 2, 1, -1, -2, -2, -1, 1, 2 }; int Y[] = { 1, 2, 2, 1, -1, -2, -2, -1 }; int count = 0; // Check if each possible move is valid or not for (int i = 0; i < 8; i++) { // Position of knight after move int x = p + X[i]; int y = q + Y[i]; // count valid moves if (x >= 0 && y >= 0 && x < n && y < m && mat[x][y] == 0) count++; } // Return number of possible moves return count; } // Driver program to check findPossibleMoves() public static void main(String[] args) { int mat[][] = { { 1, 0, 1, 0 }, { 0, 1, 1, 1 }, { 1, 1, 0, 1 }, { 0, 1, 1, 1 } }; int p = 2, q = 2; System.out.println(findPossibleMoves(mat, p, q)); } } |
C#
// C# program to find number of // possible moves of knight using System; class GFG { static int n = 4; static int m = 4; // To calculate // possible moves static int findPossibleMoves(int [,]mat, int p, int q) { // All possible moves // of a knight int []X = { 2, 1, -1, -2, -2, -1, 1, 2 }; int []Y = { 1, 2, 2, 1, -1, -2, -2, -1 }; int count = 0; // Check if each possible // move is valid or not for (int i = 0; i < 8; i++) { // Position of knight // after move int x = p + X[i]; int y = q + Y[i]; // count valid moves if (x >= 0 && y >= 0 && x < n && y < m && mat[x, y] == 0) count++; } // Return number // of possible moves return count; } // Driver Code static public void Main () { int [,]mat = { { 1, 0, 1, 0 }, { 0, 1, 1, 1 }, { 1, 1, 0, 1 }, { 0, 1, 1, 1 }}; int p = 2, q = 2; Console.WriteLine(findPossibleMoves(mat, p, q)); } } // This code is contributed by m_kit |
PHP
<?php // PHP program to find number // of possible moves of knight $n = 4; $m = 4; // To calculate possible moves function findPossibleMoves($mat, $p, $q) { global $n; global $m; // All possible moves // of a knight $X = array(2, 1, -1, -2, -2, -1, 1, 2); $Y = array(1, 2, 2, 1, -1, -2, -2, -1); $count = 0; // Check if each possible // move is valid or not for ($i = 0; $i < 8; $i++) { // Position of // knight after move $x = $p + $X[$i]; $y = $q + $Y[$i]; // count valid moves if ($x >= 0 && $y >= 0 && $x < $n && $y < $m && $mat[$x][$y] == 0) $count++; } // Return number // of possible moves return $count; } // Driver Code $mat = array(array(1, 0, 1, 0), array(0, 1, 1, 1), array(1, 1, 0, 1), array(0, 1, 1, 1)); $p = 2; $q = 2; echo findPossibleMoves($mat, $p, $q); // This code is contributed by ajit ?> |
Output:
4
References:
https://en.wikipedia.org/wiki/Knight_(chess)
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
leave a comment
1 Comments