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 some
square (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 Format
The 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
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();
}
}
