提答训练

「NOI2014」消除游戏 95pts

「NOI2006」聪明的导游 100pts

「NOI2010」成长快乐 89pts

「UNR#1」果冻运输 100pts

消除游戏

真丢人,玩了整两天…

case1 10pts

手玩就行了。

case2 10pts

发现长度限制在 8,那么我们预处理出来 $10^8$ 以内所有质数以及回文串的贡献,爆搜即可。

或者写个辅助程序手玩也可以,感觉手玩应该要比爆搜快不少。

case 3 & 4 10pts

可以发现回文串和质数串的贡献是一样的,同时是在 $100 \times 100$ 的矩形里抽出来 $500 \times 18$ 个串,在最优情况下还会剩余不少的格子,那么我们直接考虑抽取所有的质数就行了,$18$ 位质数用 Miller-Rabin 加速判断。

#include <bits/stdc++.h>

using namespace std;

#define ll             long long
#define db            double
#define up(i,j,n)        for (int i = j; i <= n; i++)
#define down(i,j,n)    for (int i = j; i >= n; i--)
#define cadd(a,b)        a = add (a, b)
#define cpop(a,b)        a = pop (a, b)
#define cmul(a,b)        a = mul (a, b)
#define pr            pair<int, int>
#define fi            first
#define se            second
#define SZ(x)        (int)x.size()
#define bin(i)        (1 << (i))
#define Auto(i,node)    for (int i = LINK[node]; i; i = e[i].next)

template<typename T> inline bool cmax(T & x, T y){return y > x ? x = y, true : false;}
template<typename T> inline bool cmin(T & x, T y){return y < x ? x = y, true : false;}
template<typename T> inline T dmax(T x, T y){return x > y ? x : y;}
template<typename T> inline T dmin(T x, T y){return x < y ? x : y;}

inline int lrand(int l, int r) { return l + (ll)rand() * rand() % (r - l + 1); }

const int MAXN = 1e3 + 5;
const int oo = 0x3f3f3f3f;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

int A[] = {2, 3, 5, 7, 11, 13, 17};

ll mod;

inline ll add(ll a, ll b) {a += b; return a >= mod ? a - mod : a;}
inline ll pop(ll a, ll b) {a -= b; return a < 0 ? a + mod : a;}

ll mul(ll a, ll b){
    ll c = 0;
    while (b) {
        if (b & 1) cadd(c, a);
        cadd(a, a); b >>= 1;
    }
    return c;
}

ll qpow(ll a, ll b){
    ll c = 1;
    while (b) {
        if (b & 1) cmul(c, a);
        cmul(a, a); b >>= 1;
    }
    return c;
}

bool chk(ll a, ll n){
    mod = n;
    ll x = mod - 1;
    while (x % 2 == 0) x >>= 1;
    ll w = qpow(a, x);
    if (w == 1 || w == mod - 1) return 1;
    while (x < n) {
        w = mul(w, w); x <<= 1;
        if (w == mod - 1) return 1;
    }
    return 0;
}

bool isprime(ll n){
    if (n == 1) return 0;
    up (i, 0, 6) {
        if (A[i] == n) return 1;
        if (!chk(A[i], n)) return 0;
    }
    return 1;
}

int N, M, K, L, R, c1, c2, F, a[MAXN][MAXN], siz;

vector<pr> ans[MAXN];

inline bool chk(int x, int y){
    if (x == 0 || x == N + 1) return 0;
    if (y == 0 || y == M + 1) return 0;
    if (a[x][y] == -1) return 0;
    return 1;
}

bool Go(int x, int y, int n, ll cur){
    int tmp = a[x][y];
    a[x][y] = -1;
    if (n == 1) {
        if (isprime(cur)) {
            ans[siz].push_back(make_pair(x, y));
            return 1;
        }
        a[x][y] = tmp;
        return 0;
    }
    bool vaild = 0;
    up (i, 0, 3) {
        int tx = x + dx[i], ty = y + dy[i];
        if (!chk(tx, ty)) continue;
        if (vaild |= Go(tx, ty, n - 1, cur * 10 + a[tx][ty])) break;
    }
    if (vaild) ans[siz].push_back(make_pair(x, y));
    else a[x][y] = tmp;
    return vaild;
}

void Fix(){
    while (true) {
        bool vaild = 0;
        up (i, 1, N - 1) up (j, 1, M) 
        if (a[i][j] != -1 && a[i + 1][j] == -1) 
        swap(a[i + 1][j], a[i][j]), vaild = 1;
        if (!vaild) break;
    }
}

int main(){
#ifdef cydiater
    freopen("input.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    scanf("%d%d%d%d%d%d%d%d", &N, &M, &K, &L, &R, &c1, &c2, &F);
    srand(time(0));
    up (i, 1, N) up (j, 1, M) scanf("%d", &a[i][j]); 
    int Case = K; siz = 0;
    while (Case--) {
        int T = 3;
        siz++;
        bool vaild = 0;
        while (T--) {
            up (i, 1, N) if (!vaild) up (j, 1, M) 
            if (a[i][j] > 0 && lrand(0, 5) == 0) {
                if (vaild |= Go(i, j, R, a[i][j])) break;
            } 
            if (vaild) break;
        }
        if (!vaild) siz--; 
        Fix();
    }
    printf("%d\n", siz);
    cerr << siz << endl;
    up (i, 1, siz) {
        printf("%d ", SZ(ans[i]));
        down (j, SZ(ans[i]) - 1, 0) printf("%d %d ", ans[i][j].fi, ans[i][j].se);
        puts("");
    }
    return 0;
}

case5 9pts

发现限制和 case2 是相似的,采用一样的策略就行了。

case6 & 7 10pts

只能抽取一次,同时质数串无贡献,长度限制在 $1000$,那么我们直接枚举回文重心,爆搜出来长度最长的合法的回文串即可,可以通过随机方向数组的访问顺序来提高搜索的效率,棋盘上的数字可以看做是 $0/1$ + 一些障碍,直观感受一下可以发现合法的状态非常少,直接搜很快可以出解。

#include <bits/stdc++.h>

using namespace std;

#define ll             long long
#define db            double
#define up(i,j,n)        for (int i = j; i <= n; i++)
#define down(i,j,n)    for (int i = j; i >= n; i--)
#define cadd(a,b)        a = add (a, b)
#define cpop(a,b)        a = pop (a, b)
#define cmul(a,b)        a = mul (a, b)
#define pr            pair<int, int>
#define fi            first
#define se            second
#define SZ(x)        (int)x.size()
#define bin(i)        (1 << (i))
#define Auto(i,node)    for (int i = LINK[node]; i; i = e[i].next)

template<typename T> inline bool cmax(T & x, T y){return y > x ? x = y, true : false;}
template<typename T> inline bool cmin(T & x, T y){return y < x ? x = y, true : false;}
template<typename T> inline T dmax(T x, T y){return x > y ? x : y;}
template<typename T> inline T dmin(T x, T y){return x < y ? x : y;}

const int MAXN = 1e3 + 5;
const int oo = 0x3f3f3f3f;
const int stdans = 16350;
const int MAXM = 2e6;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

int ord[] = {0, 1, 2, 3};

int N, M, K, L, R, F, c1, c2, a[MAXN][MAXN];
bool vis[MAXN][MAXN];

inline int lrand(int l, int r) { return l + (ll)rand() * rand() % (r - l + 1); }

pr pre[MAXM], suf[MAXM], ppre[MAXM], ssuf[MAXM];

inline bool chk(int x, int y){
    if (x == 0 || x == N + 1) return 0;
    if (y == 0 || y == M + 1) return 0;
    if (vis[x][y]) return 0;
    return 1;
}

int DFS(int xa, int ya, int xb, int yb, int d){
    pre[d] = make_pair(xa, ya);
    suf[d] = make_pair(xb, yb);
    if (d + d >= stdans) {
        up (i, 1, d) ppre[i] = pre[i], ssuf[i] = suf[i];
        return 1;
    }
    vis[xa][ya] = 1;
    vis[xb][yb] = 1;
    int sum = 0;
    bool en = 0;
    up (i, 0, 3) {
        int xc = xa + dx[ord[i]], yc = ya + dy[ord[i]];
        if (!chk(xc, yc)) continue;
        down (j, 3, 0) {
            int xd = xb + dx[ord[j]], yd = yb + dy[ord[j]];
            if (!chk(xd, yd)) continue;
            if (xc == xd && yc == yd) continue;
            if (a[xc][yc] != a[xd][yd]) continue;
            cmax(sum, DFS(xc, yc, xd, yd, d + 1) + 1);
            if ((sum + d) * 2 >= stdans) en = 1;
        }
        if (en) break;
    }
    return sum;
}

int main(){
#ifdef cydiater
    freopen("input.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    srand(time(0));
    scanf("%d%d%d%d%d%d%d%d", &N, &M, &K, &L, &R, &c1, &c2, &F);
    up (i, 1, N) up (j, 1, M) scanf("%d", &a[i][j]);
    int Case = 50000000;
    int ans = 0;
    while (Case--) {
        if (lrand(0, 4)) random_shuffle(ord, ord + 4);
        up (i, 1, N) up (j, 1, M) vis[i][j] = 0;
        int x = lrand(1, N), y = lrand(1, M), tx = x, ty = y;
        if (lrand(0, 1)) tx = x + 1;
        else if (lrand(0, 1)) ty = y + 1;
        if (!chk(tx, ty)) continue;
        if (a[tx][ty] != a[x][y]) continue;
        int w = DFS(x, y, tx, ty, 1);
        if (cmax(ans, w * 2)) {
//            up (i, 1, w) ppre[i] = pre[i], ssuf[i] = suf[i];
            cerr << ans << endl;
        }
        if (ans >= stdans) break;
        if (Case % 1000 == 0) cerr << "Case : " << Case << endl;
    }
    cerr << ans << endl;
    puts("1");
    printf("%d\n", ans);
    int m = (ans) / 2;
    down (i, m, 1) printf("%d %d ", ppre[i].fi, ppre[i].se);
    up (i, 1, m) printf("%d %d ", ssuf[i].fi, ssuf[i].se);
    puts("");
    return 0;
}

这个爆搜看起来很好写,但是其实我最开始几次都写错了,导致跑出来的解一直存在一些奇怪的问题,浪费了不少时间。这说明提答中的爆搜程序也需要精细实现。

case8 & 9 9pts + 7pts

发现情况是类似的,质数串的贡献可以忽略,只看回文的部分即可,调整一下上面的程序跑一段时间就能跑出高分解。

看别人博客发现一些小 trick,对于下发的数据点来说,如果不好直接看出来是否存在循环节,那么我们给他压缩一下,如果前后大小差 10 倍以上,那么这个数据点大概率存在循环节之类的情况。

case10 10pts

一个长回文串,直接构造一下。

聪明的导游

这道题答还是比较简单的,送了不少分。

每个点大概观察一下发现特殊性是不强的,后两个点是树,直接两边跑一下 BFS 求出直径即可,这样就有 20 分。

怎么实现通用解呢,状态数是非常多的,直接爆搜肯定没啥前途。根据后面两个点的启发,我们可以随机生成一个树,然后在上面跑求直径的算法,如果边的数量不太多还是有大概率得到高分的。

所以每次随机一下边的顺序,然后跑 kruskal 生成树。这样的话前两个点可以跑出满分,但是后面的点就萎了,这个时候就有了 40+ 分。

然后把每次随机边的顺序换成模拟退火,每个点调一下参数,跑五六分钟就能跑出高分解,这时候可以搞到 90 分。

然后尝试了各种调整,没啥结果,就去看题解了。

大体方向还是生成一棵树,然后找到直径。直观感受一下可以发现,度数总体上更少的图大概率上能比度数更多的图产生更多的贡献。我们用类似树剖的方法,每次扩展度数最少的点,度数相同的点以一定概率扩展,然后回溯回来时再依次扩展其他点即可。

#include <bits/stdc++.h>

using namespace std;

#define ll             long long
#define db            double
#define up(i,j,n)        for (int i = j; i <= n; i++)
#define down(i,j,n)    for (int i = j; i >= n; i--)
#define cadd(a,b)        a = add (a, b)
#define cpop(a,b)        a = pop (a, b)
#define cmul(a,b)        a = mul (a, b)
#define pr            pair<int, int>
#define fi            first
#define se            second
#define SZ(x)        (int)x.size()
#define bin(i)        (1 << (i))
#define Auto(i,node)    for (int i = LINK[node]; i; i = e[i].next)

template<typename T> inline bool cmax(T & x, T y){return y > x ? x = y, true : false;}
template<typename T> inline bool cmin(T & x, T y){return y < x ? x = y, true : false;}
template<typename T> inline T dmax(T x, T y){return x > y ? x : y;}
template<typename T> inline T dmin(T x, T y){return x < y ? x : y;}

inline int lrand(int l, int r) { return l + (ll)rand() * rand() % (r - l + 1); }

const int MAXN = 1e5 + 5;
const int oo = 0x3f3f3f3f;

int N, M, deg[MAXN], _deg[MAXN];
bool vis[MAXN];

struct edge {
    int y, next;
}e[MAXN << 1];

int LINK[MAXN], len = 0;

vector<int> G[MAXN];

inline void ins(int x, int y){
    e[++len].next = LINK[x]; LINK[x] = len;
    e[len].y = y;
}

inline void Ins(int x, int y){
    ins(x, y);
    ins(y, x);
}

void ers(){
    up (i, 1, N) vis[i] = 0, LINK[i] = 0;
    up (i, 1, N) deg[i] = _deg[i];
    len = 0;
}

void DFS(int node){
    vis[node] = 1;
    up (i, 0, SZ(G[node]) - 1) --deg[G[node][i]];
    int nxt = -1, mn = oo;
    up (i, 0, SZ(G[node]) - 1) if (!vis[G[node][i]]) {
        if (cmin(mn, deg[G[node][i]])) nxt = G[node][i];
        else if (mn == deg[G[node][i]] && lrand(0, 1)) 
            nxt = G[node][i]; 
    }
    if (nxt != -1) {
        Ins(node, nxt);
        DFS(nxt);
    }
    up (i, 0, SZ(G[node]) - 1) if (!vis[G[node][i]]) {
        Ins(node, G[node][i]);
        DFS(G[node][i]);
    }
}

int pre[MAXN], dis[MAXN];

deque<int> q;

int get(int ss){
    up (i, 1, N) dis[i] = oo;
    dis[ss] = 0; q.push_back(ss);
    while (!q.empty()) {
        int node = q.front(); q.pop_front();
        Auto (i, node) if (cmin(dis[e[i].y], dis[node] + 1)) 
            q.push_back(e[i].y), pre[e[i].y] = node;
    }
    int tt = ss;
    up (i, 1, N) if (dis[i] != oo && dis[i] > dis[tt]) 
            tt = i;
    return tt;
}

int n, ans[MAXN];

int main(){
#ifdef cydiater
    freopen("input.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    srand(time(0));
    scanf("%d%d", &N, &M);
    up (i, 1, M) {
        int x, y; scanf("%d%d", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
        _deg[x]++;
        _deg[y]++;
    }
    int Case = 1e5;
    while (Case--) {
        ers();
        int ss = lrand(1, N), tt;
        DFS(ss);
        ss = get(ss); tt = get(ss);
        if (cmax(n, dis[tt] + 1)) {
            cerr << n << endl;
            n = dis[tt] + 1;
            up (i, 1, n) {
                ans[i] = tt;
                tt = pre[tt];
            }
        }
        if (Case % 1000 == 0) 
            cerr << "Case : " << Case << endl;
    }
    cerr << n << endl;
    printf("%d\n", n);
    up (i, 1, n) printf("%d\n", ans[i]);
    return 0;
}

成长快乐

这种题当然就先去退个火啦,但是发现这样只能生成前三个点的高分解,总共大概就是四五十分吧。然后尝试观察后面几个点的性质,可以发现第四个点是一个线段,然后上面零散分布一些虾米,同时这些虾米都是不动的。尝试 DP 搞一搞没搞出来,然后心态爆炸去看题解了。

发现好像就是贪心搜一搜就可以的样子….那好吧。

大概就是对每个点定义其贡献为其增加的价值除以到达他的时间,每次取最大的,同时以一定概率取那些小的,用类似模拟退火的方式实现,这样每个点跑个五六分钟就可以啦。

#include <bits/stdc++.h>

using namespace std;

#define ll             long long
#define db            double
#define up(i,j,n)        for (int i = j; i <= n; i++)
#define down(i,j,n)    for (int i = j; i >= n; i--)
#define cadd(a,b)        a = add (a, b)
#define cpop(a,b)        a = pop (a, b)
#define cmul(a,b)        a = mul (a, b)
#define pr            pair<db, db>
#define fi            first
#define se            second
#define SZ(x)        (int)x.size()
#define bin(i)        (1 << (i))
#define Auto(i,node)    for (int i = LINK[node]; i; i = e[i].next)

template<typename T> inline bool cmax(T & x, T y){return y > x ? x = y, true : false;}
template<typename T> inline bool cmin(T & x, T y){return y < x ? x = y, true : false;}
template<typename T> inline T dmax(T x, T y){return x > y ? x : y;}
template<typename T> inline T dmin(T x, T y){return x < y ? x : y;}

const db eps = 1e-8;
const db oo = 2e18;

const int MAXN = 1e5 + 5;
const int W = 1e9;

inline int lrand(int l, int r) { return l + (ll)rand() * rand() % (r - l + 1); }

inline int dcmp(db x){
    if (fabs(x) < eps) return 0;
    return x < 0 ? -1 : 1;
}

inline pr operator + (const pr & a, const pr & b) { return make_pair(a.fi + b.fi, a.se + b.se); }
inline pr operator - (const pr & a, const pr & b) { return make_pair(a.fi - b.fi, a.se - b.se); }
inline pr operator * (const pr & a, const db & v) { return make_pair(a.fi * v, a.se * v); }

inline db crs(const pr & a, const pr & b) { return a.fi * b.se - a.se * b.fi; }
inline db dot(const pr & a, const pr & b) { return a.fi * b.fi + a.se * b.se; }
inline db length(const pr & a) { return dot(a, a); }

inline db sqr(db x) {return x * x;} 

struct sta {
    pr o; db w;
    inline sta () {}
    inline sta (pr o, db w) : o(o), w(w) {}
}ss, cur;

struct plan {
    db t, x, y;
    int o;
}_ans[MAXN], ans[MAXN];

int m, _m;

db tim, mxv, all;

int N;

struct fish {
    pr o, v;
    db w, t;
    int id;
    void calc() {
        pr xx = o + (v * tim);
        db dx = xx.fi - cur.o.fi, dy = xx.se - cur.o.se;
        db A = sqr(v.fi) + sqr(v.se) - sqr(mxv);
        db B = 2 * v.fi * dx + 2 * v.se * dy;
        db C = sqr(dx) + sqr(dy);
        db delta = sqr(B) - 4 * A * C;
        if (dcmp(delta) < 0) t = oo;
        else {
            if (dcmp(A) == 0) {
                if (dcmp(B) == 0) t = oo;
                else t = -C / B;
            }else {
                db p = (-B - sqrt(delta)) / (A + A);
                db q = (-B + sqrt(delta)) / (A + A);
                if (dcmp(p) >= 0) t = p;
                else if (dcmp(q) >= 0) t = q;
                else t = oo;
            }
        }    
    }
    inline bool operator < (const fish & b) const { return w * b.t * b.t > b.w * t * t; }
}a[MAXN], w[MAXN]; 

bool vis[MAXN];


int main(){
#ifdef cydiater
    freopen("input.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    srand(time(0));
    scanf("%lf%lf%lf%lf%lf", &ss.w, &mxv, &all, &ss.o.fi, &ss.o.se);
    scanf("%d", &N);
    up (i, 1, N) scanf("%lf%lf%lf%lf%lf", &a[i].w, &a[i].o.fi, &a[i].o.se, &a[i].v.fi, &a[i].v.se), a[i].id = i;
    int Case = 100;
    db ans_v = 0;
    while (Case--) {
        if (Case % 10 == 0) 
        cerr << "======== " << Case << " ========" << endl;
        db T = W - lrand(1, W), sum = 0; tim = 0; m = 0;
        up (i, 1, N) vis[i] = 0;
        cur = ss;
        while (true) {
            int n = 0;
            up (i, 1, N) if (!vis[a[i].id]) {
                if (dcmp(cur.w - a[i].w) <= 0) continue;
                w[++n] = a[i];
                w[n].calc();
                if (dcmp(tim + w[n].t - all) > 0) n--;
            }
            if (n == 0) break;
            sort(w + 1, w + n + 1);
            up (i, 1, n) {
                if (lrand(0, W) < T) {
                    T /= 3;
                    continue;
                }
                if (dcmp(w[i].t + tim - T) <= 0) {
                    tim += w[i].t;
                    cur.o = w[i].o + (w[i].v * tim);
                    cur.w += w[i].w;
                    sum += w[i].w;
                    m++;
                    ans[m].t = tim;
                    ans[m].x = cur.o.fi;
                    ans[m].y = cur.o.se;
                    ans[m].o = w[i].id;
                    vis[w[i].id] = 1;
                }
                break;
            }
        }
        if (cmax(ans_v, sum)) {
            cerr << ans_v << endl;
            _m = m;
            up (i, 1, m) _ans[i] = ans[i];
        }
    }
    cerr << ans_v << endl;
    printf("%d\n", _m);
    printf("%.10lf\n", ans_v);
    up (i, 1, _m) printf("%.10lf %.10lf %.10lf %d\n", 
    _ans[i].t, _ans[i].x, _ans[i].y, _ans[i].o);
    return 0;
}

果冻运输

最开始傻逼写了个模拟器手玩,玩了 15 分玩不下去了,观察了后几个数据点没啥特殊性质,也想不出来怎么精妙的搜,就去看题解了。

题解就是 A* 搜一下就行了…..真不知道出题人出这种题什么心态。

#include <bits/stdc++.h>

using namespace std;

#define ll             long long
#define ull            unsigned long long
#define db            double
#define up(i,j,n)        for (int i = j; i <= n; i++)
#define down(i,j,n)    for (int i = j; i >= n; i--)
#define cadd(a,b)        a = add (a, b)
#define cpop(a,b)        a = pop (a, b)
#define cmul(a,b)        a = mul (a, b)
#define pr            pair<int, int>
#define fi            first
#define se            second
#define SZ(x)        (int)x.size()
#define bin(i)        (1 << (i))
#define Auto(i,node)    for (int i = LINK[node]; i; i = e[i].next)

template<typename T> inline bool cmax(T & x, T y){return y > x ? x = y, true : false;}
template<typename T> inline bool cmin(T & x, T y){return y < x ? x = y, true : false;}
template<typename T> inline T dmax(T x, T y){return x > y ? x : y;}
template<typename T> inline T dmin(T x, T y){return x < y ? x : y;}

const int MAXN = 35;
const int MAXM = 1005;
const int dx[] = {0, 0, 2, -2};
const int dy[] = {-2, 2, 0, 0};
const int okruntime = 5 * 60 * CLOCKS_PER_SEC;
const int oo = 0x3f3f3f3f;

const ull step = 171717;

int N, M, nn, mm;
pr ID[MAXN][MAXN];

deque<pr> q;

bool vis[MAXN][MAXN];

char _s[MAXN][MAXN];

struct opera {
    int x, y, o;
    inline opera (int x = 0, int y = 0, int o = 0) :
        x(x), y(y), o(o) {}
};

struct sta {

    char s[MAXN][MAXN];

    int cur, cnt;
    ull hs;

    vector<opera> ans;

    inline bool operator == (const sta & w) const {
        up (i, 0, nn) up (j, 0, mm) if (s[i][j] != w.s[i][j]) return 0;
        return 1;
    }

    inline bool operator < (const sta & w) const { 
        return 1;
    }

    inline bool operator > (const sta & w) const {
        return 0;
    }

    void out(){
        puts("");
        up (i, 0, nn) {
            up (j, 0, mm) putchar(s[i][j]);
            puts("");
        }
        puts("");
    }

    void DFS(int x, int y){
        if (vis[x][y]) return;
        vis[x][y] = 1;
        up (i, 0, 3) {
            int tx = x + dx[i], ty = y + dy[i];
            if (tx < 0 || tx > nn) continue;
            if (ty < 0 || ty > mm) continue;
            int mx = (x + tx) / 2, my = (y + ty) / 2;
            if (s[mx][my] != '-' && s[mx][my] != '|') continue;
            if (s[tx][ty] != s[x][y]) continue;
            if (vis[tx][ty]) continue;
            DFS(tx, ty);
        }
    }

    void calc(){
        up (i, 0, nn) up (j, 0, mm) vis[i][j] = 0;
        cnt = 0;
        up (i, 0, nn) up (j, 0, mm) 
        if ('0' < s[i][j] && s[i][j] < '9' && !vis[i][j]) {
            DFS(i, j);
            cnt++;
        } 
        hs = 0;
        up (i, 0, nn) up (j, 0, mm) hs = hs * step + s[i][j];
    }

    inline char getc() {
        char ch = getchar();
        if (ch == '\n') return getc();
        if (ch == '\r') return getc();
        return ch;
    }

    bool chkmove(int sx, int sy, int ww){
        while (!q.empty()) q.pop_front();
        up (i, 0, nn) up (j, 0, mm) vis[i][j] = 0;
        q.push_back(make_pair(sx, sy));
        vis[sx][sy] = 1;
        assert('0' < s[sx][sy] && s[sx][sy] <= '9');
        while (!q.empty()) {
            pr w = q.front(); q.pop_front();
            int x = w.fi, y = w.se;
            if (s[x][y] == '0') return 0;
            up (o, 0, 3) {
                int tx = x + dx[o], ty = y + dy[o];
                int mx = (x + tx) / 2, my = (y + ty) / 2;
                if (tx < 0 || tx > nn) continue;
                if (ty < 0 || ty > mm) continue;
                if (s[tx][ty] == '.') continue;
                vis[mx][my] = 1;
                if (o == ww && s[tx][ty] == '0') return 0;
                if (vis[tx][ty]) continue;
                if (s[mx][my] == '|' || s[mx][my] == '-' || 
                o == ww) {
                    vis[tx][ty] = 1;
                    q.push_back(make_pair(tx, ty));
                }
            } 
        }
        return 1;
    }

    bool move(int sx, int sy, int o){
        if (!chkmove(sx, sy, o)) return 0;
        up (i, 0, nn) up (j, 0, mm) {
            if (vis[i][j]) {
                _s[i][j] = (i % 2 == 0 && j % 2 == 0) ? '.' : ' ';
            }else _s[i][j] = s[i][j];
        }
        up (i, 0, nn) up (j, 0, mm) if (vis[i][j]) 
            _s[i + dx[o]][j + dy[o]] = s[i][j];
        up (i, 0, nn) up (j, 0, mm) s[i][j] = _s[i][j];
        if (o < 2) 
        ans.push_back(opera(ID[sx][sy].fi, ID[sx][sy].se, o)), cur++;
        return 1;
    }

    void fall(){
        bool okfall = 1;
        while (okfall) {
            okfall = 0;
            up (i, 0, nn) if (!okfall) 
            up (j, 0, mm) if ('0' < s[i][j] && s[i][j] <= '9') {
                if (move(i, j, 2)) {
                    okfall = 1;
                    break;
                }
            }
        }
        up (i, 0, nn) up (j, 0, mm) 
        if ('0' < s[i][j] && s[i][j] < '9') up (o, 0, 3) {
            int x = i + dx[o], y = j + dy[o];
            if (x < 0 || x > nn) continue;
            if (y < 0 || y > mm) continue;
            if (s[i][j] != s[x][y]) continue;
            int mx = (i + x) / 2, my = (j + y) / 2;
            s[mx][my] = o <= 1 ? '-' : '|';
        }
        calc();
    }

    void init() {
        scanf("%d%d", &N, &M);
        nn = (N - 1) << 1; mm = (M - 1) << 1;
        cur = cnt = 0;
        up (i, 0, nn) up (j, 0, mm)
            s[i][j] = getc();
        calc();
        int cx = 1, cy = 1;
        for (int x = (N - 1) * 2; x >= 0; x -= 2) {
            for (int y = 0; y <= (M - 1) * 2; y += 2)
                ID[x][y] = make_pair(cy++, cx);
            cx++;
            cy = 1;
        }
    }

}ss, ans;

deque<sta> pq;

unordered_map<ull, bool> vis_sta;

int alphabet = 0;

bool chk[15];

int main(){
#ifdef cydiater
    freopen("input.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    ss.init();
    up (i, 0, nn) up (j, 0, mm) if ('0' < ss.s[i][j] && ss.s[i][j] < '9')
        if (!chk[ss.s[i][j] - '0']) {
            alphabet++;
            chk[ss.s[i][j] - '0'] = 1;
        }
    int a1, a2;
    scanf("%d%d", &a1, &a2);
    pq.push_back(ss); vis_sta[ss.hs] = 1;
    ans.cur = oo;
    while (!pq.empty()) {
        sta cur = pq.front(); pq.pop_front();
        if (cur.cnt == alphabet && cmin(ans.cur, cur.cur)) {
            ans = cur;
            cerr << ans.cur << endl;
        } 
        if (clock() > okruntime) break;
        up (i, 0, nn) up (j, 0, mm) 
        if ('0' < cur.s[i][j] && cur.s[i][j] <= '9') up (k, 0, 1) {
            sta nxt = cur;
            if (nxt.move(i, j, k)) {
                nxt.fall();
                if (vis_sta[nxt.hs]) continue;
                vis_sta[nxt.hs] = 1;
                pq.push_back(nxt);
            }
        }
    }
    up (i, 0, SZ(ans.ans) - 1) {
        printf("%d %d %d\n", ans.ans[i].x, ans.ans[i].y, ans.ans[i].o);
        continue;
        printf("[%d]\n", i + 1);
        int x = ans.ans[i].x, y = ans.ans[i].y, o = ans.ans[i].o;
        up (xx, 0, nn) up (yy, 0, mm) if (ID[xx][yy] == make_pair(x, y)) {
            ss.move(xx, yy, o);
            ss.fall();
            ss.out();
        }
    }
    return 0;
}