# Google CodeJam Round D APAC Test

Problem A:

Vincenzo decides to make cube IV but only has the budget to make a square maze. Its a perfect maze, every room is in the form of a square and there are 4 doors (1 on each side of the room). There is a big number written in the room. A person can only move from one room to another if the number in the next room is larger than the number in his current room by 1. Now, Vincenzo assigns unique numbers to all the rooms (1, 2, 3, .... S2) and then places S2 people in the maze, 1 in each room where S is the side length of the maze. The person who can move maximum number of times will win. Figure out who will emerge as the winner and the number of rooms he will be able to move.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of S which is the side length of the square maze. Then S2 numbers follow like a maze to give the numbers that have been assigned to the rooms.

1 2 9
5 3 8
4 6 7

Output

For each test case, output one line containing "Case #x: r d", where x is the test case number (starting from 1), r is the room number of the person who will win and d is the number of rooms he could move. In case there are multiple such people, the person who is in the smallest room will win.

Limits

1 ≤ T ≤ 100. Small dataset

1 ≤ S ≤ 10 Large dataset

1 ≤ S ≤ 10^3.

Sample

Input:

2

2
3 4
1 2

3
1 2 9
5 3 8
4 6 7

Output:

Case #1: 1 2
Case #2: 6 4

I solved this by the following code:

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>

int cube(int **a, int i, int j, int num, int n, int d[])
{
int moves=0;

if(d[num] >= 0)
return d[num];

if(i+1<n && a[i+1][j] == num+1)
{
moves = 1+cube(a,i+1,j,a[i+1][j],n,d);
if(d[num] < moves)
d[num] = moves;
return moves;
}
if(j+1<n && a[i][j+1] == num+1)
{
moves = 1+cube(a,i,j+1,a[i][j+1],n,d);
if(d[num] < moves)
d[num] = moves;
return moves;
}
if(i-1>=0 && a[i-1][j] == num+1)
{
moves = 1+cube(a,i-1,j,a[i-1][j],n,d);
if(d[num] < moves)
d[num] = moves;
return moves;
}
if((j-1>=0 && a[i][j-1] == num+1))
{
moves = 1+cube(a,i,j-1,a[i][j-1],n,d);
if(d[num] < moves)
d[num] = moves;
return moves;
}
d[num] = 0;
return 0;
}

int main()
{
int T;
FILE *fp = fopen("A-large-practice.in","r");
FILE *fo = fopen("one.txt","w+");
fscanf(fp,"%d",&T);
int N,M;

int i=0,j=0,k=0;
int c = 1;
int max=0,max_index=1;
int **a;
int **count;

while(T>0){
fscanf(fp,"%d",&N);
M=N;
i = 0;
k = 0;
a = (int **)malloc((N+1)*sizeof(int *));
count = (int **)malloc((N+1)*sizeof(int *));
for(i=0;i<M;i++){
a[i] = (int *)malloc((N+1)*sizeof(int));
count[i] = (int *)malloc((N+1)*sizeof(int));
}

/* Get input matrix */
while(N>0)
{
for(i=0;i<M;i++)
fscanf(fp,"%d",&a[k][i]);
k++;
N--;
}

/* Memoization array? */
int *d = (int *)malloc((M+1)*(M+1)*sizeof(int));
for(i=0;i<(M+1)*(M+1);i++)
d[i] = -1;

for(i=0;i<M;i++)
{
for(j=0;j<M;j++)
{
count[i][j] = cube(a,i,j,a[i][j],M,d);
if(max<count[i][j]){
max = count[i][j];
max_index = a[i][j];
}
else if(max==count[i][j] && max_index>a[i][j])
max_index=a[i][j];
}
}

fprintf(fo,"Case #%d: %d %d",c,max_index,max+1);
max=0;
max_index=1;

T--;
c++;
fprintf(fo,"\n");

/* Freeing the memory */
for(i=0;i<M;i++){
free(a[i]);
free(count[i]);
}
free(a);
free(count);
free(d);
}

return 0;
}


The code passed for both small and large test cases.

My question:

1. Is my method DP or just recursion. I have a d[] matrix that remembers the values for each number in the matrix and returns immediately if we have already seen the number. Is this not Memoization? Or only if we solve by iteratively using for loops, it is called DP?

2. Any other suggestions on the code? or any optimizations I could do?

• I think the problem is much simpler than a DP or recursive solution. You only need to find for each number, whether or not it is connected to its next highest number. You can scan the maze once, recording the result for each number in a separate array. For example, 1 1 0 1 0 1 1 1 0 for your first example. Then you find the longest chain of 1s in the array.
– JS1
Commented Nov 15, 2014 at 11:21

## 1 Answer

One optimization is that, you can check the rooms from the one with the largest number. and then check the rooms with smaller numbers. In this way, every time you want to know the number of rooms that can be accessed, you just need to add the values of the four rooms around the current one(with the number increased by 1). In this way, it's very clear that it's a $O(S^2)$ solution.