AOJ0091

問題:Blur

解法:DFS
適当にやると計算量とメモリが爆発しそうなので、無駄に枝をはやさないように気をつける。
左上から右下に向かう落としかたに限定して、行単位で全部消えない場合はそこで探索をうちやめる。
盤面のコピーはとらず１つの盤面を使い回す（再帰だとこれが簡単にできて良い）。
答えは順不同かつ１つ見つければ良いため、解が見つかった時点で答えを出力しながら戻れば良い。
再帰苦手だったが、時間かければこれくらいは自力で書けるようになった。

#include<iostream>
#include<vector>
#include<map>
using namespace std;
#define rep(i,n) for(int i=0; i<n; ++i)

const int N = 10;
int c,n;
vector<vector<int> > F;
int SS[] = {3, 3, 5};
int SC[] = {5, 9, 13};
int S[3][5][5] = {
    {
        {0, 1, 0, 0, 0},
        {1, 1, 1, 0, 0},
        {0, 1, 0, 0, 0},
        {0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0}
    },
    {
        {1, 1, 1, 0, 0},
        {1, 1, 1, 0, 0},
        {1, 1, 1, 0, 0},
        {0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0}
    },
    {
        {0, 0, 1, 0, 0},
        {0, 1, 1, 1, 0},
        {1, 1, 1, 1, 1},
        {0, 1, 1, 1, 0},
        {0, 0, 1, 0, 0}
    }
};

bool is_inside(int x, int y){
    return x >= 0 && y>= 0 && x<N && y<N;
}

bool fall(int x, int y, int size){
    if(!(is_inside(x,y) and is_inside(x+SS[size]-1, y+SS[size]-1)))return false;
    rep(i,SS[size])rep(j,SS[size])if(!(F[y+i][x+j] >= S[size][i][j]))return false;
    rep(i,SS[size])rep(j,SS[size])F[y+i][x+j] -= S[size][i][j];
    c -= SC[size];
    return true;
}

void undo(int x, int y, int size){
    rep(i,SS[size])rep(j,SS[size])F[y+i][x+j] += S[size][i][j];
    c += SC[size];
}

bool hasline(int y){
    rep(x,N)if(F[y][x] >= 1)return true;
    return false;
}

bool is_clear(){
    return c==0;
}

bool dfs(int x, int y, int depth){
    if(is_clear()) return depth == 0;
    if(depth <=0)return false;
    if(!is_inside(0, y))return false;

    if(!hasline(y))return dfs(0, y+1, depth);

    for(int i=x; i<N; ++i)rep(s,3){
        if(fall(i, y, s)){
            if(dfs(i, y, depth-1)){
                cout << i+SS[s]/2 << " " << y+SS[s]/2 << " " << s+1 << endl;
                return true;
            }
            undo(i, y, s);
        }
    }
    return false;
}

int main(){
    cin >> n;
    F = vector<vector<int> >(N, vector<int>(N));
    rep(i,N)rep(j,N){
        cin >> F[i][j];
        c += F[i][j];
    }
    dfs(0,0,n);
    return 0;
}