HackerRank Digits Square Board problem solution

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("First\n");
            else log.write("Second\n");
        }
        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("First\n"); else printf("Second\n");

   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("Second\n");
        else printf("First\n");
    }
    return 0;
}