AOJ 0243 Filling Game

問題文

Filling Game

感想

この位置にあるしどうせ枝刈り全探索だと思って適当に15分くらいで書いて投げたらなぜか通ってしかも自分以外に1人しか通ってなかったので???ってなった。(まあ本番とはテストケース違うけど)

運良かったのか。こういう怪しいの何も考えないときの方が通る気がする。

解法

基本的にバックトラックで全探索。ただし以下のような枝刈りはする。

• 今見つけた解の値以上になったら探索やめる(自明な枝刈り)
• 色変更したとき1つもセル巻き込めなかったら探索打ち切り
• 盤面書き換えにmemcpy使うことできっと爆速(知らんけどたぶんmemcpy本当に速い)

で通った。memcpyのおかげかは知らない。

ソース

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <cmath>
#include <map>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <algorithm>
using namespace std;
 
char bt[10][10];
char ne[10][10];
bool dn[10][10];
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};
int W,H;
 
 
void chg(int x,int y,char a,char b){
    if( x < 0 || x >= W || y < 0 || y >= H || bt[y][x] != b || dn[y][x]) return;
    dn[y][x] = true;
    ne[y][x] = a;
    for(int i = 0 ; i < 4 ; i++){
        chg(x+dx[i],y+dy[i],a,b);
    }
}
 
int ans = 0;
int dfs(int r){
    if( r >= ans ){
        //cout << r << endl;
        return 0;
    }
    int f = true;
 
    for(int i = 0 ; i < H ; i++){
        for(int j = 0 ; j < W ; j++){
            if(bt[i][j] != bt[0][0]){
                f = false;
                goto en;
            }
        }
    }
    en:;
     
    if( f ){
        ans = r;
        return 0;
    }
    char tmp[10][10];
    bool prev[10][10];
    memcpy(prev,dn,sizeof(dn));
    memcpy(tmp,bt,sizeof(tmp));
    for(int i = 0 ; i < 3 ; i++){
        memcpy(ne,bt,sizeof(ne));
        memset(dn,0,sizeof(dn));
        int f = false;
        if( "RGB"[i] != bt[0][0] ){
            chg(0,0,"RGB"[i],bt[0][0]);
            for(int i = 0 ; i < H ; i++){
                for(int j = 0 ; j < W ; j++)
                if(prev[i][j] != dn[i][j]) f = true;
            }
            memcpy(bt,ne,sizeof(ne));
            if(f)dfs(r+1);
            memcpy(bt,tmp,sizeof(tmp)); 
        }
    }
}
int main(){
    int n;
    while(cin >> W >> H && W){  
        memset(dn,0,sizeof(dn));
         
        for(int i = 0 ; i < H ; i++)
            for(int j = 0 ; j < W ; j++)
                cin >> bt[i][j];
        ans = 1e7;
        dfs(0);
        cout << ans << endl;
    }
     
}