In this HackerRank Digits Square Board problem solution we have given the value of N and the respective numbers written in each (i,j) cell of the board, determine whether the person who wins the game is the first or second person to move. Assume both players move optimally.
Problem solution in Java.
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class DigitsSquareBoard {
static final int max = 60;
static final int maxn = 30;
static int[][]a;
static int n;
static int[][][][]g;
public static void main(String[] args) throws IOException{
new DigitsSquareBoard().run();
}
public void run() throws IOException{
Scanner in = new Scanner(System.in);
BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
int t = in.nextInt();
int i,j,k,l,m;
a = new int[maxn][maxn];
g = new int[max][max][max][max];
for(int tt =0;tt < t;tt++){
n = in.nextInt();
for(i=0;i<n;i++){
Arrays.fill(a[i],-1);
}
for(i=0;i<n;i++){
for(j=0;j<n;j++){
m = in.nextInt();
a[i][j]=(m==2||m==3||m==5||m==7)?0:1;//0 == black primes
}
}
for(i=0;i<max;i++){
for(j=0;j<max;j++){
for(k=0;k<max;k++){
for(l=0;l<max;l++){
g[i][j][k][l]=-1;
}
}
}
}
int nimsum = grundy(0,0,n-1,n-1);
if(nimsum>0) log.write("Firstn");
else log.write("Secondn");
}
log.flush();
}
public boolean prime(int x, int y, int z, int t){
int i,j;
for(i=x;i<=z;i++){
for(j=y;j<=t;j++){
if(a[i][j]==1) return false;
}
}
return true;
}
public int grundy(int x, int y, int z, int t){
if (g[x][y][z][t]!=-1) return g[x][y][z][t];
if (prime(x,y,z,t)) {
g[x][y][z][t]=0;
return 0;
}
ArrayList<Integer> min = new ArrayList<Integer>();
int i,j,k;
for(i=x+1;i<=z;i++){
k = grundy(x,y,i-1,t)^grundy(i,y,z,t);
if(!min.contains(k)) min.add(k);
}
for(i=y+1;i<=t;i++){
k = grundy(x,y,z,i-1)^grundy(x,i,z,t);
if(!min.contains(k)) min.add(k);
}
for(k=0;min.contains(k);k++);
g[x][y][z][t]=k;
return k;
}
}
Problem solution in C++.
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
const int M=60;
int a[M][M],gr[M][M][M][M];
int n,t;
int prime_check(int x, int y, int z, int m)
{
for (int i=x;i<=z;i++)
for (int j=y;j<=m;j++)
if (a[i][j]==1 || a[i][j]==4 || a[i][j]==6 || a[i][j]==8 || a[i][j]==9) return 0;
return 1;
}
int grundy(int x, int y, int z,int m)
{
int v[75];
if (gr[x][y][z][m]!=-1) return gr[x][y][z][m];
if (prime_check(x,y,z,m))
{
gr[x][y][z][m]=0;
return 0;
}
for (int i=0;i<75;i++)
v[i]=0;
for (int i=x+1;i<=z;i++) v[grundy(x,y,i-1,m)^grundy(i,y,z,m)]=1;
for (int i=y+1;i<=m;i++) v[grundy(x,y,z,i-1)^grundy(x,i,z,m)]=1;
for (int i=0;i<75;i++)
if (v[i]==0)
{
gr[x][y][z][m]=i;
return gr[x][y][z][m];
}
return -1;
}
void solve()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
for (int k=1;k<=n;k++)
for (int l=1;l<=n;l++)
gr[i][j][k][l]=-1;
grundy(1,1,n,n);
if (gr[1][1][n][n]!=0) printf("Firstn"); else printf("Secondn");
return;
}
int main()
{
scanf("%d",&t);
while(t--)
solve();
return 0;
}
Problem solution in C.
#include <stdio.h>
#define N 35
int b[N][N], SG[N][N][N][N], pl[N][N][N][N];
int isprime(int d) {
return (d==2) || (d==3) || (d==5) || (d==7);
}
int getSG(int i, int j, int k, int l) {
int x, SGT[2*N];
if(SG[i][j][k][l]!=-1) return SG[i][j][k][l];
if(!pl[i][j][k][l]) {
SG[i][j][k][l]=0;
return 0;
}
for(x=0; x<2*N; x++) SGT[x]=0;
for(x=i; x<k; x++) SGT[getSG(i,j,x,l)^getSG(x+1,j,k,l)]=1;
for(x=j; x<l; x++) SGT[getSG(i,j,k,x)^getSG(i,x+1,k,l)]=1;
for(x=0; SGT[x]!=0; x++);
SG[i][j][k][l]=x;
return x;
}
int main() {
int i, j, k, l, n, ncases;
for(scanf("%d", &ncases); ncases>0; ncases--) {
scanf("%d", &n);
for(i=0; i<n; i++) for(j=0; j<n; j++) scanf("%d", &b[i][j]);
for(i=0; i<n; i++) for(j=0; j<n; j++)
for(k=i; k<n; k++) for(l=j; l<n; l++) {
pl[i][j][k][l]=0;
if(k>i && pl[i][j][k-1][l]) pl[i][j][k][l]=1;
if(l>j && pl[i][j][k][l-1]) pl[i][j][k][l]=1;
if(!isprime(b[k][l])) pl[i][j][k][l]=1;
}
for(i=0; i<n; i++) for(j=0; j<n; j++)
for(k=i; k<n; k++) for(l=j; l<n; l++) {
SG[i][j][k][l]=-1;
}
for(i=0; i<n; i++) for(j=0; j<n; j++)
for(k=i; k<n; k++) for(l=j; l<n; l++) {
fflush(stdout);
SG[i][j][k][l]=getSG(i,j,k,l);
}
if(SG[0][0][n-1][n-1]==0) printf("Secondn");
else printf("Firstn");
}
return 0;
}