HackerRank Fairy Chess problem solution YASH PAL, 31 July 2024 In this HackerRank Fairy Chess problem solution we have given the layout of the chessboard, can you determine the number of ways a leaper can move M times within the chessboard? Problem solution in Java. 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(); } } {“mode”:”full”,”isActive”:false} Problem solution in C++. #include<stdio.h> #include<string.h> const int MOD = 1000000007; int s, n, m; int P[700][700], S[700][700], K1[700][700], K2[700][700]; char g[250][250]; void go(int n, int s) { for(int i=250; i<255+n+s; i++) { for(int j=245-s; j<255+n+s; j++) { S[i][j] = (0ll + S[i-1][j-1] + S[i-1][j+1] - S[i-2][j] + P[i][j] + P[i-1][j] + MOD) % MOD; K1[i][j] = K1[i-1][j-1] + P[i][j]; if(K1[i][j] >= MOD) K1[i][j] -= MOD; K2[i][j] = K2[i-1][j+1] + P[i][j]; if(K2[i][j] >= MOD) K2[i][j] -= MOD; } } for(int i=250+n-1; i>=250; i--) { for(int j=250; j<250+n; j++) { if(g[i-250][j-250] != 'P') { P[i][j] = (0ll + S[i+s][j] - S[i-1][j-s-1] - S[i-1][j+s+1] + S[i-s-2][j] - K1[i-1][j+s] - K2[i-1][j-s] + K1[i-s-1][j] + K2[i-s-1][j] - P[i-s-1][j] + MOD * 5ll) % MOD; } else { P[i][j] = 0; } } } } int main() { int ntest; scanf("%d", &ntest); for(int test = 1; test <= ntest; test++) { scanf("%d%d%d", &n, &m, &s); memset(P, 0, sizeof(P)); memset(S, 0, sizeof(S)); for(int i=0; i<n; i++) { scanf("%s", g[i]); for(int j=0; j<n; j++) { if(g[i][j] == 'L') P[i+250][j+250]=1; } } for(int i=0; i<m; i++) { go(n, s); } int ans = 0; for(int i=250; i<250+n; i++) for(int j=250; j<250+n; j++) { ans = ans + P[i][j]; if(ans >= MOD) ans -= MOD; } printf("%dn", ans); } return 0; } {“mode”:”full”,”isActive”:false} Problem solution in C. /* 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("%dn", sum); } return 0; } {“mode”:”full”,”isActive”:false} algorithm coding problems