HackerRank Fairy Chess Problem Solution Yashwant Parihar, August 6, 2023August 1, 2024 In this post, we will solve HackerRank Fairy Chess Problem Solution. Let’s play Fairy Chess!You have an n x n chessboard. An s-leaper is a chess piece which can move from somesquare (xo, yo) to some square (x1,y1) if abs(xo-x1)+abs(yo – Y1) ≤ 8; however, its movements are restricted to up (†), down (), left (<), and right (→) within the confines of the chessboard, meaning that diagonal moves are not allowed. In addition, the leaper cannot leap to any square that is occupied by a pawn.Given the layout of the chessboard, can you determine the number of ways a leaper can move m times within the chessboard?Note: abs(x) refers to the absolute value of some integer,..Input FormatThe first line contains an integer, q, denoting the number of queries. Each query is described as follows: The first line contains three space-separated integers denoting n. m. and s. respectively. Each line i of the n subsequent lines contains n characters. The jth character in the jth line describes the contents of square (i, j) according to the following key:indicates the location is empty.P indicates the location is occupied by a pawn. L indicates the location of the leaper. Output Format For each query, print the number of ways the leaper can make m moves on a new line. Because this value can be quite large, your answer must be modulo 10 power 9 + 7. Sample Input 0 3 4 1 1 .... .L.. .P.. .... 3 2 1 ... ... ..L 4 3 2 .... ...L ..P. P... Sample Output 0 4 11 385 HackerRank Fairy Chess Problem Solution Fairy Chess C Solution /* Enter your code here. Read input from STDIN. Print output to STDOUT */ #include <stdlib.h> #include <stdio.h> #include <strings.h> #define MAX_WIDTH 200 #define MAX_MOVE 201 #define MODULAR 1000000007 #define FORMAT_RESULT(x) if (x >= MODULAR) {\ x -= MODULAR;\ } else if (x < 0) {\ x += MODULAR;\ } char board[MAX_WIDTH][MAX_WIDTH]; int width; int max_step; int max_moves; int result[MAX_MOVE][MAX_WIDTH][MAX_WIDTH] = {0}; int cache_asc[2][MAX_WIDTH][MAX_WIDTH]; int cache_desc[2][MAX_WIDTH][MAX_WIDTH]; int read_index; int write_index; void compute(int moves) { int y, x, x1, y1, y2, x2, dx, dy; for (y = 0; y < max_step; y++) { result[moves][0][0] += cache_desc[read_index][y][0]; FORMAT_RESULT(result[moves][0][0]); } if (max_step < width) { result[moves][0][0] += cache_desc[read_index][max_step][0]; FORMAT_RESULT(result[moves][0][0]); } else { if (1 < width) { result[moves][0][0] += cache_desc[read_index][max_step - 1][1]; FORMAT_RESULT(result[moves][0][0]); } } cache_desc[write_index][0][0] = cache_asc[write_index][0][0] = board[0][0] == 'P' ? 0 : result[moves][0][0]; for (x = 1; x < width; x++) { result[moves][0][x] = result[moves][0][x - 1]; x1 = x; y1 = max_step; if (y1 >= width) { dy = y1 - width + 1; y1 -= dy; x1 += dy; } if (x1 < width) { result[moves][0][x] += cache_desc[read_index][y1][x1]; FORMAT_RESULT(result[moves][0][x]); } x1 = x - 1; y1 = max_step; if (y1 >= width) { dy = y1 - width + 1; y1 -= dy; x1 -= dy; } if (x1 >= 0) { result[moves][0][x] -= cache_asc[read_index][y1][x1]; FORMAT_RESULT(result[moves][0][x]); } cache_desc[write_index][0][x] = cache_asc[write_index][0][x] = board[0][x] == 'P' ? 0 : result[moves][0][x]; } for (y = 1; y < width; y++) { for (x = 0; x < width; x++) { result[moves][y][x] = result[moves][y - 1][x]; x1 = x; y1 = y + max_step; x2 = x + max_step; y2 = y; if (y1 >= width) { dy = y1 - width + 1; y1 -= dy; x1 += dy; } if (x1 < width) { if (x2 >= width - 1) { result[moves][y][x] += cache_desc[read_index][y1][x1]; FORMAT_RESULT(result[moves][y][x]); } else { result[moves][y][x] += cache_desc[read_index][y1][x1] - cache_desc[read_index][y2 - 1][x2 + 1]; FORMAT_RESULT(result[moves][y][x]); } } x1 = x; y1 = y + max_step; x2 = x - max_step; y2 = y; if (y1 >= width) { dy = y1 - width + 1; y1 -= dy; x1 -= dy; } if (x1 >= 0) { if (x2 <= 0) { result[moves][y][x] += cache_asc[read_index][y1][x1]; FORMAT_RESULT(result[moves][y][x]); } else { result[moves][y][x] += cache_asc[read_index][y1][x1] - cache_asc[read_index][y2 - 1][x2 - 1]; FORMAT_RESULT(result[moves][y][x]); } } if (y + max_step < width) { result[moves][y][x] -= result[moves - 1][y + max_step][x]; FORMAT_RESULT(result[moves][y][x]); } x1 = x + max_step; y1 = y - 1; x2 = x; y2 = y - 1 - max_step; if (x1 >= width) { dx = x1 - width + 1; y1 -= dx; x1 -= dx; } if (y1 >= 0) { if (y2 <= 0 || x2 == 0) { result[moves][y][x] -= cache_asc[read_index][y1][x1]; FORMAT_RESULT(result[moves][y][x]); } else { result[moves][y][x] -= cache_asc[read_index][y1][x1] - cache_asc[read_index][y2 - 1][x2 - 1]; FORMAT_RESULT(result[moves][y][x]); } } x1 = x - max_step; y1 = y - 1; x2 = x; y2 = y - 1 - max_step; if (x1 < 0) { dx = -x1; x1 += dx; y1 -= dx; } if (y1 >= 0) { if (y2 <= 0 || x2 == width - 1) { result[moves][y][x] -= cache_desc[read_index][y1][x1]; FORMAT_RESULT(result[moves][y][x]); } else { result[moves][y][x] -= cache_desc[read_index][y1][x1] - cache_desc[read_index][y2 - 1][x2 + 1]; FORMAT_RESULT(result[moves][y][x]); } } if (y - 1 - max_step >= 0) { result[moves][y][x] += result[moves - 1][y - 1 - max_step][x]; FORMAT_RESULT(result[moves][y][x]); } cache_asc[write_index][y][x] = x > 0 ? cache_asc[write_index][y - 1][x - 1] : 0; cache_desc[write_index][y][x] = (x < width - 1) ? cache_desc[write_index][y - 1][x + 1] : 0; if (board[y][x] != 'P') { cache_desc[write_index][y][x] += result[moves][y][x]; FORMAT_RESULT(cache_desc[write_index][y][x]); cache_asc[write_index][y][x] += result[moves][y][x]; FORMAT_RESULT(cache_asc[write_index][y][x]); } } } for (y = 0; y < width; y++) { for (x = 0; x < width; x++) { if (board[y][x] == 'P') { result[moves][y][x] = 0; } } } } int main (int argc, char *argv[]) { int num_case; int x, y, moves, sum, i, j; scanf("%d", &num_case); while (num_case--) { bzero(result, sizeof(int) * MAX_MOVE * MAX_WIDTH * MAX_WIDTH); bzero(cache_asc, sizeof(int) * 2 * MAX_WIDTH * MAX_WIDTH); bzero(cache_desc, sizeof(int) * 2 * MAX_WIDTH * MAX_WIDTH); scanf("%d %d %d", &width, &max_moves, &max_step); for (y = width - 1; y >= 0; y--) { scanf("%s", board[y]); } read_index = 0; write_index = 1; for (y = 0; y < width; y++) { for (x = 0; x < width; x++) { if (board[y][x] == 'L') { result[0][y][x] = 1; } if (x > 0 && y > 0) { cache_asc[read_index][y][x] = result[0][y][x] + cache_asc[read_index][y - 1][x - 1]; } else { cache_asc[read_index][y][x] = result[0][y][x]; } if (x < width && y > 0) { cache_desc[read_index][y][x] = result[0][y][x] + cache_desc[read_index][y - 1][x + 1]; } else { cache_desc[read_index][y][x] = result[0][y][x]; } } } for (moves = 1; moves <= max_moves; moves++) { compute(moves); if (read_index == 1) { write_index = 1; read_index = 0; } else { write_index = 0; read_index = 1; } } sum = 0; for (y = 0; y < width; y++) { for (x = 0; x < width; x++) { sum += result[max_moves][y][x]; FORMAT_RESULT(sum); } } printf("%d\n", sum); } return 0; } Fairy Chess C++ Solution #include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> #include <cstring> using namespace std; class Imp { public: static const int MOD = 1000000007; typedef long long LL; int u; Imp(int v = 0):u(v) {} operator int& () { return u; } operator const int& () const { return u; } Imp operator + (int v) const { return u + v < MOD ? u + v : u + v - MOD; } Imp operator - (int v) const { return u < v ? u - v + MOD : u - v; } Imp operator * (int v) const { return u * LL(v) % MOD; } Imp operator / (int v) const { return u * RR(v) % MOD; } Imp operator - () const { return u ? MOD - u : 0; } Imp& operator += (int v) { u += u + v < MOD ? v : v - MOD; return *this; } Imp& operator -= (int v) { u -= u < v ? v - MOD : v; return *this; } Imp& operator *= (int v) { u = u * LL(v) % MOD; return *this; } Imp& operator /= (int v) { u = u * RR(v) % MOD; return *this; } static LL RR(int x) { return x > 1 ? RR(MOD % x) * (MOD - MOD / x) % MOD : x; } }; #define MAX 200 // rotated chess board char board[MAX * 2][MAX * 2]; Imp dp[MAX][MAX * 2][MAX * 2]; // square area from (0, 0) to (i, j) Imp areas[MAX * 2][MAX * 2]; void happy(int N, int M, int S) { memset(dp, 0, sizeof(dp)); memset(areas, 0, sizeof(areas)); memset(board, 'P', sizeof(board)); // read map for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { int ii = i; int jj = j; int x = ii - jj + N - 1; int y = ii + jj; char c = getchar(); // init dp[0, x, y] if (c == 'L') { dp[0][x][y] = 1; // update areas for (int a = x; a < N * 2 - 1; a++) { for (int b = y; b < N * 2 - 1; b++) { areas[a][b] = 1; } } } board[x][y] = c; } // eat linefeed getchar(); } for (int m = 1; m <= M; m++) { for (int i = 0; i < N * 2 - 1; i++) { for (int j = 0; j < N * 2 - 1; j++) { int xstart = max(0, i - S); int ystart = max(0, j - S); int xend = min(i + S, N * 2 - 2); int yend = min(j + S, N * 2 - 2); // cannot place on pawn if (board[i][j] == 'P') continue; // square area dp[m][i][j] = areas[xend][yend]; if (xstart - 1 >= 0 && ystart - 1 >= 0) { dp[m][i][j] += areas[xstart - 1][ystart - 1]; } if (xstart - 1 >= 0) { dp[m][i][j] -= areas[xstart - 1][yend]; } if (ystart - 1 >= 0) { dp[m][i][j] -= areas[xend][ystart - 1]; } } } // update areas areas[0][0] = dp[m][0][0]; for (int i = 1; i < N * 2 - 1; i++) { // first row areas[0][i] = areas[0][i - 1] + dp[m][0][i]; // first column areas[i][0] = areas[i - 1][0] + dp[m][i][0]; } for (int i = 1; i < N * 2 - 1; i++) { for (int j = 1; j < N * 2 - 1; j++) { areas[i][j] = dp[m][i][j]; areas[i][j] += areas[i - 1][j] + areas[i][j - 1] - areas[i - 1][j - 1]; } } } // sum up Imp moves = 0; for (int i = 0; i < N * 2 - 1; i++) { for (int j = 0; j < N * 2 - 1; j++) { moves += dp[M][i][j]; } } cout << moves.u << endl; } int main() { int cas; scanf("%d", &cas); while (cas--) { int N, M, S; scanf("%d %d %d\n", &N, &M, &S); happy(N, M, S); } return 0; } Fairy Chess C Sharp Solution using System; using System.Collections.Generic; using System.Text; class Solution { static void Main(string[] args) { int T = ReadNextInt(); for (int t = 0; t < T; t++) { int n = ReadNextInt(); int m = ReadNextInt(); int s = ReadNextInt(); Init(n, s); Position L = new Position(); for (int x = 0; x < n; x++) { for (int y = 0; y < n; y++) { switch(ReadNextChar()) { case 'P': SetPawn(new Position(x, y)); break; case 'L': L = new Position(x,y); break; } } } var result = Go(m, L); Console.WriteLine(result); } } private static int N; private static int S; private static bool[] PAWNS; private static void Init(int n, int s) { N = n; S = s; PAWNS = new bool[N * N]; } private static void SetPawn(Position pos) { PAWNS[pos.Key] = true; } private struct Position { public readonly int X; public readonly int Y; public Position(int x, int y) { this.X = x; this.Y = y; } public static int GetKey(int x, int y) { return y * N + x; } public int Key { get { return GetKey(this.X, this.Y); } } public override string ToString() { return string.Format("x:{0} y:{1}", this.X, this.Y); } } private class Cache { private Count[] cache; private Count[] index; public Cache() { this.cache = new Count[N * N]; this.index = new Count[(N + S) * N]; } public void Clear() { Array.Clear(this.cache, 0, this.cache.Length); Array.Clear(this.index, 0, this.index.Length); } public Count this[Position pos] { get { int key = pos.Key; return this.cache[key]; } set { int key = pos.Key; this.cache[key] = value; } } public static TimeSpan ALL = new TimeSpan(); public static long CNTR = 0; public void BuildIndex(Cache current) { var NOW = DateTime.Now; var index = this.index; var cache = this.cache; //Console.WriteLine(); //Console.WriteLine("Building index for"); //Console.WriteLine(PrintArray(cache, N)); int XMinusYMinus = N + 1; int XPlusYMinus = N - 1; int X0YMinusMinus = 2 * N; int NPlusS = N + S; int NMinusOne = N - 1; int indexKey = 0; for (int y = 0; y < NPlusS; y++) { for (int x = 0; x < N; x++) { CNTR++; if (y > 0) { if (x == 0) { index[indexKey] = index[indexKey - XPlusYMinus]; } else if (x == NMinusOne) { index[indexKey] = index[indexKey - XMinusYMinus]; } else { if (y > 1) { index[indexKey] = (long)index[indexKey - XPlusYMinus].value + (long)index[indexKey - XMinusYMinus].value - (long)index[indexKey - X0YMinusMinus].value; } else { index[indexKey] = (long)index[indexKey - XPlusYMinus].value + (long)index[indexKey - XMinusYMinus].value; } } } if (y < N) { index[indexKey] += cache[Position.GetKey(x, y)]; } int yy = y - S; if (yy >= 0 && yy < N) { var pos = new Position(x, yy); if (!PAWNS[pos.Key]) { current[pos] = this.QuerySum(x, yy, index[indexKey].value); } } indexKey++; } } //Console.WriteLine(); //Console.WriteLine("Index:"); //Console.WriteLine(PrintArray(index, N)); ALL += DateTime.Now - NOW; } public long QuerySum(int x, int y, long upper) { long a = upper - IndexAt(x - S - 1, y - 1) - IndexAt(x + S + 1, y - 1) + IndexAt(x, y - S - 2); long b = IndexAt(x, y + S - 1) - IndexAt(x - S, y - 1) - IndexAt(x + S, y - 1) + IndexAt(x, y - S - 1); return a + b; } private long IndexAt(int x, int y) { if (y < 0) { return 0; } if (x < -N) { return 0; } if (x >= N * 2) { return 0; } if (x < 0) { return IndexAt(0, y + x); } if (x >= N) { return IndexAt(N - 1, y + N - x - 1); } return this.index[IndexKey(x, y)].value; } private static int IndexKey(int x, int y) { return y * N + x; } } private static string PrintArray(Count[] a, int row) { StringBuilder builder = new StringBuilder(); int i = 0; foreach (var v in a) { if (builder.Length > 0) { builder.Append((++i % row) == 0 ? Environment.NewLine : " "); } builder.AppendFormat("{0:0000}", v.value); } return builder.ToString(); } private static Count Go(int steps, Position pos) { Cache current = InitializeFirstMove(); Cache prev = new Cache(); while (steps > 0) { var t = current; current = prev; prev = t; current.Clear(); CalculateNextMove(prev, current); //Console.WriteLine("Steps: " + steps); steps--; } return current[pos]; } private static void CalculateNextMove(Cache previous, Cache current) { previous.BuildIndex(current); } private static Cache InitializeFirstMove() { var cache = new Cache(); for (int x = 0; x < N; x++) { for (int y = 0; y < N; y++) { var pos = new Position(x, y); if (!PAWNS[pos.Key]) { cache[pos] = 1; } } } return cache; } private struct Count { private const int MOD = 1000000007; public readonly int value; public Count(long v) { v %= MOD; if (v < 0) v = MOD + v; this.value = (int)v; } public override string ToString() { return this.value.ToString(); } public static implicit operator Count(long l) { return new Count(l); } public static Count operator +(Count a, Count b) { return new Count((long)a.value + (long)b.value); } public static Count operator -(Count a, Count b) { if (a.value >= b.value) return new Count((long)a.value - (long)b.value); return new Count((long)MOD + (long)a.value - (long)b.value); } public static Count operator *(Count a, Count b) { return new Count((long)a.value * (long)b.value); } } private static int ReadNextInt() { int c = Console.Read(); while (!char.IsDigit((char)c)) { c = Console.Read(); } int value = 0; do { value *= 10; value += (int)(c - '0'); } while (char.IsDigit((char)(c = Console.Read()))); return value; } private static int ReadNextChar() { int c = Console.Read(); while (c != '.' && c != 'P' && c != 'L') { c = Console.Read(); } return c; } } Fairy Chess Java Solution import java.io.*; import java.util.*; public class Solution { static final int MOD = 1_000_000_007; static long sum(long a, long b) { return (a + b) % MOD; } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH"))); StringTokenizer st = new StringTokenizer(br.readLine()); int q = Integer.parseInt(st.nextToken()); for (int qItr = 0; qItr < q; qItr++) { st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); int s = Integer.parseInt(st.nextToken()); int[][] A = new int[2 * n + 1][2 * n + 1]; int[][] ways = new int[2 * n + 1][2 * n + 1]; for (int i = 0; i < n; i++) { char[] item = br.readLine().toCharArray(); for (int j = 0; j < n; j++) { if (item[j] == 'P') { continue; } int x = i + j + 1; int y = n - i + j; A[x][y] = 1; if (item[j] == 'L') { ways[x][y]++; } } } for (int i = 0; i < m; i++) { int[][] past = ways; ways = new int[2 * n + 1][2 * n + 1]; for (int j = 0; j < 2 * n + 1; j++) { for (int k = 0; k < 2 * n + 1; k++) { if (j > 0) { past[j][k] = (int) sum(past[j][k], past[j - 1][k]); } if (k > 0) { past[j][k] = (int) sum(past[j][k], past[j][k - 1]); } if (j > 0 && k > 0) { past[j][k] = (int) sum(past[j][k], MOD-past[j - 1][k - 1]); } } } for (int j = 0; j < 2 * n + 1; j++) { for (int k = 0; k < 2 * n + 1; k++) { if (A[j][k] == 0) continue; int x1 = Math.max(j - s, 0); int x2 = Math.min(j + s, 2 * n); int y1 = Math.max(k - s, 0); int y2 = Math.min(k + s, 2 * n); ways[j][k] = past[x2][y2]; if (x1 > 0) { ways[j][k] = (int) sum(ways[j][k], MOD-past[x1 - 1][y2]); } if (y1 > 0) { ways[j][k] = (int) sum(ways[j][k], MOD-past[x2][y1 - 1]); } if (x1 > 0 && y1 > 0) { ways[j][k] = (int) sum(ways[j][k], past[x1 - 1][y1 - 1]); } } } } long result = 0; for (int i = 0; i < 2 * n + 1; i++) { for (int j = 0; j < 2 * n + 1; j++) { result = sum(result, ways[i][j]); } } bw.write(String.valueOf(result)); bw.newLine(); } bw.close(); br.close(); } } c C# C++ HackerRank Solutions java CcppCSharpHackerrank Solutionsjava