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(); } }
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; }
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; }