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?

HackerRank Fairy Chess problem solution


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

{"mode":"full","isActive":false}