[Luogu] Mayan游戏

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <cstring>

#include <string>

#include <iostream>

using namespace std;

const int N = ;

struct Node{int x, y, ho;} answer[N];

int n;

int a[N][N];

inline int read() {

    int x = ; char c = getchar();

    while(c < '' || c > '')c = getchar();

    while(c >= '' && c <= '')x = x *  + c - '', c = getchar();

    return x;

}

void drop() {

    int num[N][N];

    memset(num, -, sizeof(num));

    for(int i = ; i < ; i ++) {

        int h = ;

        for(int j = ; j < ; j ++) if(a[i][j]) num[i][h ++] = j;

    }

    for(int i = ; i < ; i ++)

        for(int j = ; j < ; j ++)

            a[i][j] = num[i][j] == - ?  : a[i][num[i][j]];

    return ;

}

bool empty() {

    for(int i = ; i < ; i ++) for(int j = ; j < ; j ++) if(a[i][j]) return ;

    return ;

}

bool clear() {

    bool ret_flag = ;

    for(int i = ; i < ; i ++)

        for(int j = ; j < ; j ++)

            if(a[i][j]) {

                int x = i;

                while(x <  && a[i][j] == a[x + ][j]) x ++;

                if(x - i >= ) {

                    for(int xx = i; xx <= x; xx ++) {

                        int up = j; int dn = j;

                        while(a[xx][up + ] == a[i][j] && up < ) up ++;

                        while(a[xx][dn - ] == a[i][j] && dn > ) dn --;

                        if(up - dn >= )

                            for(int y_ = dn; y_ <= up; y_ ++) a[xx][y_] = ;

                    }

                    for(int x_ = i; x_ <= x;  x_ ++) a[x_][j] = ;

                    ret_flag = ;

                }

            }

    for(int i = ; i < ; i ++)

        for(int j = ; j < ; j ++)

            if(a[i][j]) {

                int y = j;

                while(a[i][y + ] == a[i][j] && y < ) y ++;

                if(y - j >= ) {

                    for(int yy = j; yy <= y; yy ++) {

                        int lef = i; int rig = i;

                        while(a[lef - ][yy] == a[i][j] && lef > ) lef --;

                        while(a[rig + ][yy] == a[i][j] && rig < ) rig ++;

                        if(rig - lef >= )

                            for(int x_ = lef; x_ <= rig; x_ ++) a[x_][yy] = ;

                    }

                    for(int y_ = j; y_ <= y; y_ ++) a[i][y_] = ;

                    ret_flag = ;

                }

            }

    if(ret_flag) return ;

    else return ;

}

void dfs(int tot) {

    if(tot > n) {

        if(empty()) {

            for(int i = ; i <= n; i ++)  {

                if(answer[i].ho) printf("%d %d %d\n", answer[i].x + , answer[i].y, -);

                else printf("%d %d %d\n", answer[i].x, answer[i].y, );

            }

            exit();

        }

        return ;

    }

    int sum[N + ];

    memset(sum, , sizeof(sum));

    for(int i = ; i < ; i ++) for(int j = ; j < ; j ++) sum[a[i][j]] ++;

    for(int i = ; i <= ; i ++) if(sum[i] && sum[i] <= ) return ;

    for(int i = ; i < ; i ++)

        for(int j = ; j < ; j ++)

            if(a[i][j] != a[i + ][j]) {

                answer[tot].x = i; answer[tot].y = j; answer[tot].ho = (!a[i][j]);

                int tmp[N][N];

                memcpy(tmp, a, sizeof(tmp));

                swap(a[i][j], a[i + ][j]);

                drop();

                while(clear()) drop();

                dfs(tot + );

                answer[tot].x = ; answer[tot].y = ; answer[tot].ho = ;

                memcpy(a, tmp, sizeof(a));

            }

}

int main() {

    n = read();

    for(int i = ; i < ; i ++) {

        for(int j = ; ; j ++) {

            a[i][j] = read();

            if(!a[i][j]) break;

        }

    }

    dfs();

    printf("-1\n");

    return ;

}

/*

3

1 0

2 1 0

2 3 4 0

3 1 0

2 4 3 4 0

*/