题意
给你一个(n imes m)的矩形方格纸片，其中有些位置是洞，保证不是洞的位置连通
现在你可以沿着边界剪一剪，要求剪完了之后，纸片不能断开（不能断裂成多个连通块），然后问，剪完的纸片是否可以折成一个正方体，剪的方案是由你来决定的，也就是问，是否存在一种剪的方案，使得纸片可以折成一个正方体
正方体的一个面可以被多次覆盖
题解
不难发现，我们要剪完之后把纸片折起来，也就是说，剪完了之后，格子应该形成一个生成树
再发现，如果这个生成树的形态确定了，那么不论以什么顺序折，最后得到的立方体都是一样的
又发现，当纸片比较大的时候，总是可以折成一个正方体的
但是什么叫“纸片比较大”呢？不太清楚
于是我们考虑随机一个生成树出来，然后判断这个生成树是否可以折成一个正方体
随机10000次，如果都不行，那么就不存在这样一个方案，否则可以
这样就一举解决了“纸片大”和“纸片小”的问题
随机生成树的方法是，把边random_shuffle，然后用并查集依次把边加进来
判断一个生成树是否可行的方法也是个难点
考虑折纸的过程太复杂，因此我们考虑有一个正方体，在这个平摊开的纸片上滚来滚去，滚到一个方格上，就可以给那个面染色
如果滚完了所有格子，6个面都被染色了，就是一组解
这样判断就简单多了
代码
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii,pii> Edge;
const int N = 6;
int _w;
int n, m, a[N][N];
vector<Edge> edge;
vector<pii> adj[N][N];
namespace DSU {
int pa[N*N];
void init() {
for( int i = 0; i < N*N; ++i )
pa[i] = i;
}
int find( int u ) {
return u == pa[u] ? u : pa[u] = find( pa[u] );
}
bool link( int u, int v ) {
u = find(u), v = find(v);
if( u == v ) return false;
return pa[u] = v, true;
}
}
int face[6];
void rotate( int x, int y, int nx, int ny ) {
int tmp[6];
if( nx == x+1 ) {
tmp[0] = face[4];
tmp[5] = face[2];
tmp[1] = face[1];
tmp[3] = face[3];
tmp[4] = face[5];
tmp[2] = face[0];
} else if( nx == x-1 ) {
tmp[0] = face[2];
tmp[5] = face[4];
tmp[1] = face[1];
tmp[3] = face[3];
tmp[4] = face[0];
tmp[2] = face[5];
} else if( ny == y+1 ) {
tmp[0] = face[3];
tmp[5] = face[1];
tmp[1] = face[0];
tmp[3] = face[5];
tmp[4] = face[4];
tmp[2] = face[2];
} else if( ny == y-1 ) {
tmp[0] = face[1];
tmp[5] = face[3];
tmp[1] = face[5];
tmp[3] = face[0];
tmp[4] = face[4];
tmp[2] = face[2];
} else {
assert(0);
}
for( int i = 0; i < 6; ++i )
face[i] = tmp[i];
}
void dfs( int x, int y, int fax, int fay ) {
face[0] = 1;
for( pii nxt : adj[x][y] ) {
int nx = nxt.first;
int ny = nxt.second;
if( nx == fax && ny == fay ) continue;
rotate(x, y, nx, ny);
dfs(nx, ny, x, y);
}
if( fax != -1 ) rotate(x, y, fax, fay);
}
bool chk( int sx, int sy ) {
memset(face, 0, sizeof face);
dfs(sx, sy, -1, -1);
for( int i = 0; i < 6; ++i )
if( face[i] == 0 )
return false;
return true;
}
bool check() {
DSU::init();
for( int i = 0; i < n; ++i )
for( int j = 0; j < m; ++j )
adj[i][j].clear();
for( Edge e : edge ) {
pii u = e.first;
pii v = e.second;
int uid = u.first * N + u.second;
int vid = v.first * N + v.second;
if( DSU::link(uid, vid) ) {
adj[u.first][u.second].push_back(v);
adj[v.first][v.second].push_back(u);
}
}
for( int i = 0; i < n; ++i )
for( int j = 0; j < m; ++j )
if( a[i][j] )
return chk(i, j);
return false;
}
int main() {
int T;
_w = scanf( "%d", &T );
while( T-- ) {
_w = scanf( "%d%d", &n, &m );
for( int i = 0; i < n; ++i )
for( int j = 0; j < m; ++j ) {
char ch;
_w = scanf( " %c", &ch );
a[i][j] = ch - '0';
}
edge.clear();
for( int i = 0; i < n; ++i )
for( int j = 0; j < m; ++j ) {
if( i != n-1 && a[i][j] && a[i+1][j] ) {
edge.push_back( Edge(pii(i, j), pii(i+1, j)) );
}
if( j != m-1 && a[i][j] && a[i][j+1] ) {
edge.push_back( Edge(pii(i, j), pii(i, j+1)) );
}
}
bool yes = false;
for( int times = 0; times < 10000; ++times ) {
random_shuffle(edge.begin(), edge.end());
if( check() ) {
yes = true;
break;
}
}
puts( yes ? "Yes" : "No" );
}
return 0;
}