4997 - ABCD Tiles

4997 - ABCD Tiles
Asia - Kuala Lumpur - 2010/2011
http://acm.uva.es/archive/nuevoportal/data/problem.php?p=4997

• 問題概要

十字型のパネルを隙間無く埋めれるか。
3種類のパネルがあり、8方向に同じ種類のタイルは接してはいけない。
辞書順最小の埋め方を答えよ。
埋めれないなら埋めれないと答えよ。

• 解法

埋め方は一意に定まる。
塗り方は貪欲で一番最初に見つかったものが答え。
貪欲でやると塗れない、けど、塗り方を少し変えると塗れる場合もあることに注意。
塗るとき、ピースをグラフに落として、
グラフを彩色していく感じでやると書きやすく感じた。
（僕が考えたわけではないですが。
書きやすい実装の勉強になった。

• ソース

#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>

#define REP(i,b,n) for(int i=b;i<(int)n;i++)
#define rep(i,n)   REP(i,0,n)

using namespace std;

const int dx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int dy[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int px[] = {-1, 0, 1, 0};
const int py[] = {1, 1, 1, 2};
const int N = 15;
const string IMP = " Not Possible!";
const int E = 50;
int t[N][N], n, ID;
bool edge[E][E];
int C[E];
string ans;

bool invalid(int y, int x){
  if(x < 0 || y < 0 || x >= n || y >= n)return true;
  return false;
}

void input(){
  rep(i, n){
    rep(j, n){
      char c;
      cin >> c;
      if(c == 'A')t[i][j] = 0;
      else t[i][j] = -1;
    }
  }
  rep(i, E){
    rep(j, E){
      edge[i][j] = false;;
    }
  }
  ID = 0;
  ans = "";
  rep(i, E)C[i] = -1;
}

bool canPut(int y, int x, int &ID){
  rep(i, 4){
    int ny = y + py[i];
    int nx = x + px[i];
    if(invalid(ny, nx) || t[ny][nx] >= 0)return false;
  }
  rep(i, 4){
    int ny = y + py[i];
    int nx = x + px[i];
    t[ny][nx] = ID;
  }
  t[y][x] = ID;
  ID++;
  return true;
}

bool putID(){
  ID = 1;
  rep(i, n){
    rep(j, n){
      if(t[i][j] >= 0)continue;
      if(canPut(i, j, ID))continue;
      return false;
    }
  }
  ID--;
  return true;
}

void makeGraph(){
  rep(i, n){
    rep(j, n){
      if(t[i][j] < 1)continue;
      rep(d, 8){
        int ny = dy[d] + i;
        int nx = dx[d] + j;
        if(invalid(ny, nx))continue;
        if(t[ny][nx] == t[i][j])continue;
        if(t[ny][nx] < 1)continue;
        edge[t[i][j]-1][t[ny][nx]-1] = edge[t[ny][nx]-1][t[i][j]-1] = true;
      }
    }
  }
}

void make_ans(){
  rep(i, ID){
    ans += 'B' + C[i];
  }
}

bool solve(int pos){
  if(pos == ID){
    make_ans();
    return true;
  }
  rep(c, 3){
    bool flag = false;
    rep(i, pos){
      if(!edge[pos][i])continue;
      if(C[i] < 0)continue;
      if(c == C[i]){
        flag = true;
        break;
      }
    }
    if(flag)continue;
    C[pos] = c;
    if(solve(pos+1))return true;
    C[pos] = -1;
  }
  return false;
}

void output(){
  printf("\n");
  rep(i, n){
    rep(j, n){
      if(t[i][j] == 0){
        printf("A");
      }
      else {
        printf("%c", ans[t[i][j]-1]);
      }
    }
    printf("\n");
  }
}

int main(){
  int T;
  cin >> T;
  rep(tc, T){
    cin >> n;
    printf("Case %d:",tc+1);
    input();
    if(!putID()){
      printf("%s\n", IMP.c_str());
      continue;
    }
    makeGraph();
    if(solve(0))output();
    else printf("%s\n", IMP.c_str());
  }
  return 0;
}