AOJ : 0243 - Filling Game (塗りつぶしゲーム)

問題概要

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0243
問題文が日本語なので, 概要は省略です.

解法

TLEしないかどうか不安でしたが, 「深さ優先探索+ステップ数の勝手な上限予想」で解くことができました.

再帰の処理フロー

• 盤面の色が全て同じ色である
  • それまでにかかったステップ数が解候補
• 今見つかっている最小ステップより多く再帰している
  • 再帰打ち切ってreturn
• 左上の色と同じ色に変えても意味がないので, それ以外の2種類の色を塗って再帰

一度の再帰における分岐は, 2つしかありません. だから間に合うのでしょう.
ちなみに, 僕は上記の枝刈りに加えて, 勝手なステップ数上限予想として, 18ステップを超えたら再帰を打ち切るようにしています(テストしている間に, 18ステップを超えることはないだろうと予想したため).

プログラム

#include <iostream>
#include <queue>
#include <cstring>
#include <climits>
using namespace std;

typedef pair<int,int> P;

int w, h, ans;
int t[12][12];
bool closed[12][12];

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

bool judge(int array[12][12]){
  for(int i = 0; i < h; i++){
    for(int j = 0; j < w; j++){
      if(array[i][j] != array[0][0]){
        return false;
      }
    }
  }

  return true;
}

void show(int s[12][12]){
  for(int i = 0; i < h; i++){
    for(int j = 0; j < w; j++){
      cout<<s[i][j]<<" ";
    }
    cout<<endl;
  }
  cout<<"--\n";
}

void nextState(int from[12][12], int to1[12][12], int to2[12][12]){
  int color1, color2;
  if(from[0][0] == 0)      { color1 = 1; color2 = 2; }
  else if(from[0][0] == 1) { color1 = 0; color2 = 2; }
  else                     { color1 = 0; color2 = 1; }

  for(int i = 0; i < h; i++){
    for(int j = 0; j < w; j++){
      to1[i][j] = to2[i][j] = from[i][j];
    }
  }

  queue<P> open;
  open.push(P(0, 0));
  memset(closed, 0, sizeof(closed));
  to1[0][0] = color1;
  to2[0][0] = color2;

  while(!open.empty()){
    P p = open.front();
    open.pop();

    for(int i = 0; i < 4; i++){
      int nx = p.first + dx[i];
      int ny = p.second + dy[i];

      if(0 <= nx && nx < w && 0 <= ny && ny < h &&
        !closed[ny][nx] && from[ny][nx] == from[0][0]){
        to1[ny][nx] = color1;
        to2[ny][nx] = color2;
        closed[ny][nx] = true;
        open.push(P(nx, ny));
      }
    }
  }
}

void solve(int s[12][12], int cnt){
  if(judge(s)){
    ans = min(ans, cnt);
    return;
  }
  if(cnt >= ans){
    return;
  }

  int next1[12][12];
  int next2[12][12];

  nextState(s, next1, next2);
  solve(next1, cnt + 1);
  solve(next2, cnt + 1);
}

int main(){
  while(cin >> w >> h, w || h){
    for(int i = 0; i < h; i++){
      for(int j = 0; j < w; j++){
        char ch;
        cin >> ch;

        if(ch == 'R')      t[i][j] = 0;
        else if(ch == 'G') t[i][j] = 1;
        else if(ch == 'B') t[i][j] = 2;
      }
    }

    ans = 18;
    solve(t, 0);

    cout << ans << endl;
  }
}