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("%d\n", 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("%d\n", sum);
}
return 0;
}
0 Comments