# Tiling a grid with dominoes

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
 This problem has been solved by mlc413.
 This problem has been solved by kerry.
 This problem has been solved by hjfreyer.

 Sorter: Mlc413 GNYR ICPC 2007 http://acm.pku.edu.cn/JudgeOnline/problem?id=0000

This is problem H from the GNYR programming contest at Kean University. This problem is not yet on the Peking site See problem specs here [[1]]

The trick to this problem is realizing that tiling an area of length 4xN can be reduced to a 4xM area, with M<N. The way you do this is by making a function that returns the number of ways you can tile an area based on two factors:

1. The length of the area you're tiling
2. The relief of the area you're tiling

By relief, I mean what is "sticking out" at the end of the length. Draw out the n=3 case. You'll notice it can be reduced to the n=2 case in multiple ways, depending on what "relief" you choose for n=2. It's mostly a visual thing, so draw it out, think about it, and check out the code.

## Kerry and Melanie's Solution

```
import java.util.*;

public class Main{

public static Scanner in;

public static void main(String[] args){
in=new Scanner(System.in);

doStuff();
}

public static void doStuff(){
int N=in.nextInt();

for(int i=0;i<N;i++){
System.out.print((i+1) + " ");
solve(in.nextInt());
}
}

public static void solve(int W){
//System.out.println(W);
System.out.println(value(W));
}

public static int value (int w){
int num = 0;
if (w == 1) num = 1;
else if (w == 2) num = 5;
else if (w == 3) num = 11;
else{
num += value(w-1) + value(w-2);//these are the clean cut cases DONE
if(w %2 == 0)
{
num += 2*eVal(w-2) + eVal2(w-2);
}
else{
num += 2*oVal(w-2) + oVal2(w-2);
}
}
return num;

}

public static int eVal(int n)
{
int ans = 1;
for(int j = n; j > 0; j--)
{
ans += value(j);
}

return ans;
}

public static int eVal2(int n)
{
int ans = 1;
for(int j = n; j > 0; j-=2)
{
ans += value(j);
}

return ans;

}

public static int oVal(int n)
{
int ans = 1;
for(int j = n; j > 0; j--)
{
ans += value(j);
}

return ans;
}

public static int oVal2(int n)
{
int ans = 0;
for(int j = n; j > 0; j-=2)
{
ans += value(j);
}

return ans;

}

}

```

## Hunter's Solution

This code is a lot longer than it has to be. I chose to enumerate every possible case for clarity (any my own sanity)'s sake, rather than making it really tight. The majority of the code is just one big if statement.

```import java.util.*;

public class Main{
public static Scanner in;
public static void main(String[] args){
in = new Scanner(System.in);
doStuff();

//	System.out.println(numWays(7));
}

public static void doStuff(){
int N = in.nextInt();
for(int i = 1; i <=N; i++){
int len=in.nextInt();
num_matrix=new int[len+1][6];

for(int k=0;k<len+1;k++){
for(int j=0;j<6;j++)
num_matrix[k][j]=-1;
}

System.out.printf("%d %d\n",i,numWays(len));

}
}

public static int numWays(int len){
return numWays(len,0);
}

public static int[][] num_matrix=null;
public static int numWays(int len,int relief){
if(num_matrix[len][relief]==-1)
num_matrix[len][relief]=numWaysCalc(len,relief);
return num_matrix[len][relief];

}
public static int numWaysCalc(int len,int relief){

if(len==1){
switch(relief){
case 0:
case 1:
case 2:
case 4:
case 5:
return 1;
case 3:
return 0;
}
}

int total=0;
switch(relief){

// We have case 0
case 0:
// Leaving case 0
total+=numWays(len-1,0);

// Leaving case 1
total+= numWays(len-1,1);
// Leaving case 2
total+= numWays(len-1,2);
// Leaving case 3
total+= numWays(len-1,3);
// Leaving case 4
total+= numWays(len-1,4);
// Leaving case 5
total+=numWays(len-1,5);

// We have case 1
case 1:
// Leaving case 0
total+=numWays(len-1,0);

// Leaving case 1
total+= 0;
// Leaving case 2
total+= 0;
// Leaving case 3
total+= numWays(len-1,3);
// Leaving case 4
total+= 0;
// Leaving case 5
total+=0;

// We have case 2
case 2:
// Leaving case 0
total+=numWays(len-1,0);

// Leaving case 1
total+=0;
// Leaving case 2
total+= numWays(len-1,2);
// Leaving case 3
total+= 0;
// Leaving case 4
total+= 0;
// Leaving case 5
total+=0;

// We have case 3
case 3:
// Leaving case 0
total+=0;

// Leaving case 1
total+= 0;
// Leaving case 2
total+= 0;
// Leaving case 3
total+= 0;
// Leaving case 4
total+= numWays(len-1,4);
// Leaving case 5
total+=0;

// We have case 4
case 4:
// Leaving case 0
total+=numWays(len-1,0);

// Leaving case 1
total+= 0;
// Leaving case 2
total+= 0;
// Leaving case 3
total+= numWays(len-1,3);
// Leaving case 4
total+= 0;
// Leaving case 5
total+=0;

// We have case 0
case 5:
// Leaving case 0
total+=numWays(len-1,0);

// Leaving case 1
total+= 0;
// Leaving case 2
total+= 0;
// Leaving case 3
total+= 0;
// Leaving case 4
total+= 0;
// Leaving case 5
total+=0;