Here’s another problem that appeared on the 2011 Google Code Jam:

You are selling beautiful geometric pictures. Each one consists of 1×1 square tiles arranged into a non-overlapping grid. For example:

.##..
.####
.####
.##..

Blue tiles are represented by ‘#’ characters, and white tiles are represented by ‘.’ characters. You do not use other colors.

Not everybody likes blue though, and some customers want you to replace all the blue tiles in your picture with red tiles. Unfortunately, red tiles only come in the larger 2×2 size, which makes this tricky.

You can cover any 2×2 square of blue tiles with a single red tile, and then repeat until finished. A red tile cannot overlap another red tile, it cannot cover white tiles, and it cannot go outside the picture. For example, you could add red tiles to the previous picture as follows:

./..
.//
./\/
./..

Each red tile is represented here by a pair of ‘/’ characters in the top-left and bottom-right corners, and a pair of ” characters in the other two corners.

Given a blue and white picture, can you transform it into a red and white picture in this way?

Input

The first line of the input gives the number of test cases, T. T test cases follow.

Each test case begins with a line containing R and C, the number of rows and columns in a picture. The next R lines each contain exactly C characters, describing the picture. As above, ‘#’ characters represent blue tiles, and ‘.’ characters represent white tiles.

Output

For each test case, first output one line containing “Case #x:” where x is the case number (starting from 1).

If it is possible to cover the blue tiles with non-overlapping red tiles, output R lines each containing C characters, describing the resulting red and white picture. As above, red tiles should be represented by ‘/’ and ” characters, while white tiles are represented by ‘.’ characters. If multiple solutions are possible, you may output any of them.

If the task is impossible, output a single line containing the text “Impossible” instead.

Limits

Small dataset

1 ≤ T ≤ 20.
1 ≤ R ≤ 6.
1 ≤ C ≤ 6.

Large dataset

1 ≤ T ≤ 50.
1 ≤ R ≤ 50.
1 ≤ C ≤ 50.

Sample Input
3
2 3
###
###
1 1
.
4 5
.##..
.####
.####
.##..

Sample Output
Case #1:
Impossible
Case #2:
.
Case #3:
./..
.//
./\/
./..

My Solution

A simple greedy approach solved the problem correctly.

#include <stdio.h>

int color(char v[][50], int rows, int columns, int x, int y){
  if ((y+1<columns)&&(x+1<rows)){
    if (v[x][y+1]=='#'&&v[x+1][y]=='#'&&v[x+1][y+1]=='#'){
      v[x][y]='/';
      v[x][y+1]='\';
      v[x+1][y]='\';
      v[x+1][y+1]='/';
      return 1;
    }
    else
      return 0;
  }
  else{
    return 0;
  }
}
void print(char v[][50], int rows, int columns){
  int x,y;
  for (x=0;x<rows;x++){
    for (y=0;y<columns;y++){
      printf("%c",v[x][y]);
    }
    if (x<rows-1)
      printf("n");
  }
}

int main(){
  int i,t;
  int r,c;
  int x,y;
  char v[50][50];
  int found;
  int result;
  
  scanf("%d",&t);

  for (i=0;i<t;i++){
    if(i>0)
      printf("n");
    printf("Case #%d:n",i+1);
    scanf("%d %d",&r,&c);
    getchar();
    for (x=0;x<r;x++){
      for (y=0;y<c;y++){
        scanf("%c",&v[x][y]);
      }
      getchar();
    }

    while(1){
      found = 0;
      for (x=0;x<r;x++){
        for (y=0;y<c;y++){
          if (v[x][y]=='#'){
            found = 1;
            goto here;
          }
        }
      }
      here:
      if(found){
        result = color(v,r,c,x,y);
        if (result)
          continue;
        else{
          printf("Impossible");
          break;
        }
      }
      else{
        print(v,r,c);
        break;
      } 
    }
  }

return 0;
}