C++14(g++5.4) 解法, 执行用时: 8ms, 内存消耗: 1016K, 提交时间: 2019-01-07 17:05:17
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
using namespace std;
const int z[12]={4,2,8,1,4,8,4,8,8,1,4,8};
const int p[12][8][4][4]={
//A
{
{
{1,1,0,0},
{1,0,0,0},
{0,0,0,0},
{0,0,0,0}
},
{
{1,0,0,0},
{1,1,0,0},
{0,0,0,0},
{0,0,0,0}
},
{
{1,1,0,0},
{0,1,0,0},
{0,0,0,0},
{0,0,0,0}
},
{
{0,1,0,0},
{1,1,0,0},
{0,0,0,0},
{0,0,0,0}
}
},
//B
{
{
{1,1,1,1},
{0,0,0,0},
{0,0,0,0},
{0,0,0,0}
},
{
{1,0,0,0},
{1,0,0,0},
{1,0,0,0},
{1,0,0,0}
}
},
//C
{
{
{1,0,0,0},//1
{1,1,1,0},
{0,0,0,0},
{0,0,0,0}
},
{
{1,1,1,0},//2
{1,0,0,0},
{0,0,0,0},
{0,0,0,0}
},
{
{0,0,1,0},//3
{1,1,1,0},
{0,0,0,0},
{0,0,0,0}
},
{
{1,1,1,0},//4
{0,0,1,0},
{0,0,0,0},
{0,0,0,0}
},
{
{1,0,0,0},//5
{1,0,0,0},
{1,1,0,0},
{0,0,0,0}
},
{
{1,1,0,0},//6
{1,0,0,0},
{1,0,0,0},
{0,0,0,0}
},
{
{0,1,0,0},//7
{0,1,0,0},
{1,1,0,0},
{0,0,0,0}
},
{
{1,1,0,0},//8
{0,1,0,0},
{0,1,0,0},
{0,0,0,0}
}
},
//D
{
{
{1,1,0,0},//1
{1,1,0,0},
{0,0,0,0},
{0,0,0,0}
}
},
//E
{
{
{1,1,1,0},//1
{1,0,0,0},
{1,0,0,0},
{0,0,0,0}
},
{
{1,0,0,0},//2
{1,0,0,0},
{1,1,1,0},
{0,0,0,0}
},
{
{1,1,1,0},//3
{0,0,1,0},
{0,0,1,0},
{0,0,0,0}
},
{
{0,0,1,0},//4
{0,0,1,0},
{1,1,1,0},
{0,0,0,0}
}
},
//F
{
{
{1,1,1,1},//1
{0,1,0,0},
{0,0,0,0},
{0,0,0,0}
},
{
{1,1,1,1},//2
{0,0,1,0},
{0,0,0,0},
{0,0,0,0}
},
{
{0,1,0,0},//3
{1,1,1,1},
{0,0,0,0},
{0,0,0,0}
},
{
{0,0,1,0},//4
{1,1,1,1},
{0,0,0,0},
{0,0,0,0}
},
{
{1,0,0,0},//5
{1,1,0,0},
{1,0,0,0},
{1,0,0,0}
},
{
{1,0,0,0},//6
{1,0,0,0},
{1,1,0,0},
{1,0,0,0}
},
{
{0,1,0,0},//7
{1,1,0,0},
{0,1,0,0},
{0,1,0,0}
},
{
{0,1,0,0},//8
{0,1,0,0},
{1,1,0,0},
{0,1,0,0}
}
},
//G
{
{
{1,1,1,0},//1
{1,0,1,0},
{0,0,0,0},
{0,0,0,0}
},
{
{1,0,1,0},//2
{1,1,1,0},
{0,0,0,0},
{0,0,0,0}
},
{
{1,1,0,0},//3
{1,0,0,0},
{1,1,0,0},
{0,0,0,0}
},
{
{1,1,0,0},//4
{0,1,0,0},
{1,1,0,0},
{0,0,0,0}
}
},
//H
{
{
{1,1,1,0},//1
{1,1,0,0},
{0,0,0,0},
{0,0,0,0}
},
{
{1,1,1,0},//2
{0,1,1,0},
{0,0,0,0},
{0,0,0,0}
},
{
{1,1,0,0},//3
{1,1,1,0},
{0,0,0,0},
{0,0,0,0}
},
{
{0,1,1,0},//4
{1,1,1,0},
{0,0,0,0},
{0,0,0,0}
},
{
{1,1,0,0},//5
{1,1,0,0},
{1,0,0,0},
{0,0,0,0}
},
{
{1,0,0,0},//6
{1,1,0,0},
{1,1,0,0},
{0,0,0,0}
},
{
{0,1,0,0},//7
{1,1,0,0},
{1,1,0,0},
{0,0,0,0}
},
{
{1,1,0,0},//8
{1,1,0,0},
{0,1,0,0},
{0,0,0,0}
}
},
//I
{
{
{1,1,1,0},//1
{0,0,1,1},
{0,0,0,0},
{0,0,0,0}
},
{
{0,0,1,1},//2
{1,1,1,0},
{0,0,0,0},
{0,0,0,0}
},
{
{0,1,1,1},//3
{1,1,0,0},
{0,0,0,0},
{0,0,0,0}
},
{
{1,1,0,0},//4
{0,1,1,1},
{0,0,0,0},
{0,0,0,0}
},
{
{1,0,0,0},//5
{1,0,0,0},
{1,1,0,0},
{0,1,0,0}
},
{
{0,1,0,0},//6
{1,1,0,0},
{1,0,0,0},
{1,0,0,0}
},
{
{1,0,0,0},//7
{1,1,0,0},
{0,1,0,0},
{0,1,0,0}
},
{
{0,1,0,0},//8
{0,1,0,0},
{1,1,0,0},
{1,0,0,0}
}
},
//J
{
{
{0,1,0,0},
{1,1,1,0},
{0,1,0,0},
{0,0,0,0}
}
},
//K
{
{
{1,0,0,0},//1
{1,1,0,0},
{0,1,1,0},
{0,0,0,0}
},
{
{1,1,0,0},//2
{0,1,1,0},
{0,0,1,0},
{0,0,0,0}
},
{
{0,1,1,0},//3
{1,1,0,0},
{1,0,0,0},
{0,0,0,0}
},
{
{0,0,1,0},//4
{0,1,1,0},
{1,1,0,0},
{0,0,0,0}
}
},
//L
{
{
{1,1,1,1},//1
{0,0,0,1},
{0,0,0,0},
{0,0,0,0}
},
{
{1,1,1,1},//2
{1,0,0,0},
{0,0,0,0},
{0,0,0,0}
},
{
{1,0,0,0},//3
{1,1,1,1},
{0,0,0,0},
{0,0,0,0}
},
{
{0,0,0,1},//4
{1,1,1,1},
{0,0,0,0},
{0,0,0,0}
},
{
{1,0,0,0},//5
{1,0,0,0},
{1,0,0,0},
{1,1,0,0}
},
{
{1,1,0,0},//6
{1,0,0,0},
{1,0,0,0},
{1,0,0,0}
},
{
{1,1,0,0},//7
{0,1,0,0},
{0,1,0,0},
{0,1,0,0}
},
{
{0,1,0,0},//8
{0,1,0,0},
{0,1,0,0},
{1,1,0,0}
}
}
};
/**********************************************************/
const int N=4000,M=100,S=N*7+M;
//构建矩阵： 每个格子一个，每个形状一个
struct DLX{
int n,m,cnt;
int x[S],y[S],L[S],R[S],U[S],D[S];
int C[M],anscnt,ans[N];
void init(int c){
memset(x,0,sizeof x),memset(y,0,sizeof y);
memset(L,0,sizeof L),memset(R,0,sizeof R);
memset(U,0,sizeof U),memset(D,0,sizeof D);
memset(C,0,sizeof C),memset(ans,0,sizeof ans);
anscnt=0,m=c;
for (int i=0;i<=m;i++)
L[i]=i-1,R[i]=i+1,U[i]=D[i]=i;
L[0]=m,R[m]=0,cnt=m;
}
void link(int i,int j){
cnt++;
x[cnt]=i;
y[cnt]=j;
L[cnt]=cnt-1;
R[cnt]=cnt+1;
D[cnt]=j;
D[U[j]]=cnt;
U[cnt]=U[j];
U[j]=cnt;
C[j]++;
}
void Delete(int k){
L[R[k]]=L[k];
R[L[k]]=R[k];
for (int i=D[k];i!=k;i=D[i])
for (int j=R[i];j!=i;j=R[j]){
U[D[j]]=U[j];
D[U[j]]=D[j];
C[y[j]]--;
}
}
void Reset(int k){
L[R[k]]=k;
R[L[k]]=k;
for (int i=U[k];i!=k;i=U[i])
for (int j=L[i];j!=i;j=L[j]){
U[D[j]]=j;
D[U[j]]=j;
C[y[j]]++;
}
}
bool solve(){
if (R[0]==0)
return true;
anscnt++;
int k=R[0];
for (int i=R[k];i!=0;i=R[i])
if (C[i]<C[k])
k=i;
Delete(k);
for (int i=D[k];i!=k;i=D[i]){
ans[anscnt]=x[i];
for (int j=R[i];j!=i;j=R[j])
Delete(y[j]);
if (solve())
return true;
for (int j=L[i];j!=i;j=L[j])
Reset(y[j]);
}
Reset(k);
anscnt--;
return false;
}
}dlx;
const int L=15,n=10;
int Row;
char ch[L][L];
bool matched[12];
struct PIC{
int x,y,i,j;
}built[N];
bool match(int x,int y,int i,int j){
char CHAR=i+'A';
for (int a=0;a<4;a++)
for (int b=0;b<4;b++)
if (p[i][j][a][b]&&(x+a>n||y+b>x+a||ch[x+a][y+b]!=CHAR))
return 0;
return 1;
}
bool nmatch(int x,int y,int i,int j){
for (int a=0;a<4;a++)
for (int b=0;b<4;b++)
if (p[i][j][a][b]&&(x+a>n||y+b>x+a||ch[x+a][y+b]!='.'))
return 0;
return 1;
}
int Hash(int a,int b){
return a*(a-1)/2+b;
}
void build(int x,int y,int i,int j){
Row++;
built[Row].x=x;
built[Row].y=y;
built[Row].i=i;
built[Row].j=j;
int first=dlx.cnt+1;
for (int a=0;a<4;a++)
for (int b=0;b<4;b++)
if (p[i][j][a][b])
dlx.link(Row,Hash(x+a,y+b));
dlx.link(Row,55+i+1);
dlx.L[first]=dlx.cnt;
dlx.R[dlx.cnt]=first;
}
void addPIC(int x,int y,int i,int j){
char CHAR=i+'A';
for (int a=0;a<4;a++)
for (int b=0;b<4;b++)
if (p[i][j][a][b])
ch[x+a][y+b]=CHAR;
}
int main(){
for (int i=1;i<=n;i++)
scanf("%s",ch[i]+1);
dlx.init(55+12);
memset(matched,0,sizeof matched);
Row=0;
for (int i=1;i<=n;i++)
for (int j=1,imat=0;j<=i;imat=0,j++)
for (int x=0;x<12&&!imat;x++)
for (int y=0;y<z[x]&&!imat;y++)
if (match(i,j,x,y)){
matched[x]=imat=1;
build(i,j,x,y);
}
for (int i=1;i<=n;i++)
for (int j=1;j<=i;j++)
for (int x=0;x<12;x++){
if (matched[x])
continue;
for (int y=0;y<z[x];y++)
if (nmatch(i,j,x,y))
build(i,j,x,y);
}
bool found=dlx.solve();
if (!found)
printf("No solution");
else {
for (int i=1;i<=dlx.anscnt;i++){
int bh=dlx.ans[i];
if (!matched[built[bh].i])
addPIC(built[bh].x,built[bh].y,built[bh].i,built[bh].j);
}
for (int i=1;i<=n;puts(""),i++)
for (int j=1;j<=i;j++)
printf("%c",ch[i][j]);
}
return 0;
}
C++(clang++ 11.0.1) 解法, 执行用时: 250ms, 内存消耗: 512K, 提交时间: 2022-09-06 00:46:24
//#pragma GCC optimize("Ofast")
#include<cstdio>
#include<cstring>
const int N=10;
char ch[15];
int S,V[15];
struct node {
int x,y,v;
} A[20][20];
int dfs(node &T);
int f5(node &T1,node &T2,node &T3,node &T4,int ch,node &T) {
if (V[ch-64]||T1.v||T2.v||T3.v||T4.v) return 0;
V[T1.v=T2.v=T3.v=T4.v=T.v=ch-64]=1;
return dfs(T)?1:(V[ch-64]=T1.v=T2.v=T3.v=T4.v=T.v=0);
}
int f4(node &T1,node &T2,node &T3,int ch,node &T) {
if (V[ch-64]||T1.v||T2.v||T3.v) return 0;
V[T1.v=T2.v=T3.v=T.v=ch-64]=1;
return dfs(T)?1:(V[ch-64]=T1.v=T2.v=T3.v=T.v=0);
}
int f3(node &T1,node &T2,int ch,node &T) {
if (V[ch-64]||T1.v||T2.v) return 0;
V[T1.v=T2.v=T.v=ch-64]=1;
return dfs(T)?1:(V[ch-64]=T1.v=T2.v=T.v=0);
}
int dfs(node &T) {
if ((++S)>=5e6) return 0;
int x=T.x,y=T.y;
while (A[x][y].v&&x<=N) (++y)>x&&(y=1,++x);
if (x==N+1) return 1;
if (x!=T.x||y!=T.y) return dfs(A[x][y]);
if (f5(A[x+1][y],A[x+2][y],A[x+2][y+1],A[x+2][y+2],'E',T)) return 1;
if (f5(A[x+1][y],A[x+2][y],A[x][y+1],A[x][y+2],'E',T)) return 1;
if (f5(A[x][y+1],A[x][y+2],A[x+1][y+2],A[x+2][y+2],'E',T)) return 1;
if (y>2&&f5(A[x+1][y],A[x+2][y],A[x+2][y-1],A[x+2][y-2],'E',T)) return 1;
if (f5(A[x][y+1],A[x][y+2],A[x][y+3],A[x+1][y+1],'F',T)) return 1;
if (f5(A[x+1][y],A[x+2][y],A[x+3][y],A[x+1][y+1],'F',T)) return 1;
if (f5(A[x][y+1],A[x][y+2],A[x][y+3],A[x+1][y+2],'F',T)) return 1;
if (f5(A[x+1][y],A[x+2][y],A[x+3][y],A[x+2][y+1],'F',T)) return 1;
if (y>1&&f5(A[x+1][y],A[x+2][y],A[x+3][y],A[x+2][y-1],'F',T)) return 1;
if (y>1&&f5(A[x+1][y],A[x+2][y],A[x+3][y],A[x+1][y-1],'F',T)) return 1;
if (y>1&&f5(A[x+1][y],A[x+1][y-1],A[x+1][y+1],A[x+1][y+2],'F',T)) return 1;
if (y>2&&f5(A[x+1][y],A[x+1][y+1],A[x+1][y-1],A[x+1][y-2],'F',T)) return 1;
if (f5(A[x+1][y],A[x+1][y+1],A[x+1][y+2],A[x][y+2],'G',T)) return 1;
if (f5(A[x+1][y],A[x][y+1],A[x][y+2],A[x+1][y+2],'G',T)) return 1;
if (f5(A[x+1][y],A[x][y+1],A[x+2][y],A[x+2][y+1],'G',T)) return 1;
if (f5(A[x][y+1],A[x+1][y+1],A[x+2][y+1],A[x+2][y],'G',T)) return 1;
if (f5(A[x][y+1],A[x+1][y+1],A[x][y+2],A[x+1][y+2],'H',T)) return 1;
if (f5(A[x+1][y],A[x+2][y],A[x+1][y+1],A[x+2][y+1],'H',T)) return 1;
if (f5(A[x+1][y],A[x][y+1],A[x+1][y+1],A[x+2][y],'H',T)) return 1;
if (f5(A[x+1][y],A[x][y+1],A[x+1][y+1],A[x+2][y+1],'H',T)) return 1;
if (f5(A[x+1][y],A[x][y+1],A[x+1][y+1],A[x+1][y+2],'H',T)) return 1;
if (f5(A[x+1][y],A[x][y+1],A[x+1][y+1],A[x][y+2],'H',T)) return 1;
if (y>1&&f5(A[x+1][y],A[x+2][y],A[x+1][y-1],A[x+2][y-1],'H',T)) return 1;
if (y>1&&f5(A[x+1][y],A[x][y+1],A[x+1][y+1],A[x+1][y-1],'H',T)) return 1;
if (y>2&&f5(A[x][y+1],A[x+1][y],A[x+1][y-1],A[x+1][y-2],'I',T)) return 1;
if (y>1&&f5(A[x][y+1],A[x][y+2],A[x+1][y],A[x+1][y-1],'I',T)) return 1;
if (f5(A[x][y+1],A[x][y+2],A[x+1][y+2],A[x+1][y+3],'I',T)) return 1;
if (f5(A[x][y+1],A[x+1][y+1],A[x+1][y+2],A[x+1][y+3],'I',T)) return 1;
if (f5(A[x+1][y],A[x+2][y],A[x+2][y+1],A[x+3][y+1],'I',T)) return 1;
if (f5(A[x+1][y],A[x+1][y+1],A[x+2][y+1],A[x+3][y+1],'I',T)) return 1;
if (y>1&&f5(A[x+1][y],A[x+1][y-1],A[x+2][y-1],A[x+3][y-1],'I',T)) return 1;
if (y>1&&f5(A[x+1][y],A[x+2][y],A[x+2][y-1],A[x+3][y-1],'I',T)) return 1;
if (y>1&&f5(A[x+1][y],A[x+2][y],A[x+1][y-1],A[x+1][y+1],'J',T)) return 1;
if (f5(A[x+1][y],A[x+1][y+1],A[x+2][y+1],A[x+2][y+2],'K',T)) return 1;
if (f5(A[x][y+1],A[x+1][y+1],A[x+1][y+2],A[x+2][y+2],'K',T)) return 1;
if (y>1&&f5(A[x][y+1],A[x+1][y],A[x+1][y-1],A[x+2][y-1],'K',T)) return 1;
if (y>2&&f5(A[x+1][y],A[x+1][y-1],A[x+2][y-1],A[x+2][y-2],'K',T)) return 1;
if (f5(A[x+1][y],A[x+2][y],A[x+3][y],A[x+3][y+1],'L',T)) return 1;
if (f5(A[x+1][y],A[x+1][y+1],A[x+1][y+2],A[x+1][y+3],'L',T)) return 1;
if (f5(A[x+1][y],A[x][y+1],A[x][y+2],A[x][y+3],'L',T)) return 1;
if (f5(A[x+1][y],A[x+2][y],A[x+3][y],A[x][y+1],'L',T)) return 1;
if (f5(A[x][y+1],A[x][y+2],A[x][y+3],A[x+1][y+3],'L',T)) return 1;
if (f5(A[x][y+1],A[x+1][y+1],A[x+2][y+1],A[x+3][y+1],'L',T)) return 1;
if (y>1&&f5(A[x+1][y],A[x+2][y],A[x+3][y],A[x+3][y-1],'L',T)) return 1;
if (y>3&&f5(A[x+1][y],A[x+1][y-1],A[x+1][y-2],A[x+1][y-3],'L',T)) return 1;
if (f4(A[x+1][y],A[x+2][y],A[x+3][y],'B',T)) return 1;
if (f4(A[x][y+1],A[x][y+2],A[x][y+3],'B',T)) return 1;
if (f4(A[x][y+1],A[x][y+2],A[x+1][y+2],'C',T)) return 1;
if (f4(A[x][y+1],A[x+1][y+1],A[x+2][y+1],'C',T)) return 1;
if (f4(A[x+1][y],A[x][y+1],A[x][y+2],'C',T)) return 1;
if (f4(A[x+1][y],A[x+2][y],A[x][y+1],'C',T)) return 1;
if (f4(A[x+1][y],A[x+1][y+1],A[x+1][y+2],'C',T)) return 1;
if (f4(A[x+1][y],A[x+2][y],A[x+2][y+1],'C',T)) return 1;
if (y>1&&f4(A[x+1][y],A[x+2][y],A[x+2][y-1],'C',T)) return 1;
if (y>2&&f4(A[x+1][y],A[x+1][y-1],A[x+1][y-2],'C',T)) return 1;
if (f4(A[x+1][y],A[x][y+1],A[x+1][y+1],'D',T)) return 1;
if (y>1&&f3(A[x+1][y],A[x+1][y-1],'A',T)) return 1;
if (f3(A[x+1][y],A[x][y+1],'A',T)) return 1;
if (f3(A[x+1][y],A[x+1][y+1],'A',T)) return 1;
if (f3(A[x][y+1],A[x+1][y+1],'A',T)) return 1;
return 0;
}
int main() {
for (int i=0; i<=N+3; ++i) for (int j=0; j<=N+3; ++j) A[i][j]= {i,j,-1};
for (int i=1; i<=N; ++i) {
scanf("%s",ch+1);
for (int j=1; j<=i; ++j)
(A[i][j].v=(ch[j]=='.'?0:ch[j]-64))&&(V[ch[j]-64]=1);
}
if (!dfs(A[1][1])) return puts("No solution"),0;
for (int i=1; i<=N; ++i,putchar('\n'))
for (int j=1; j<=i; ++j) putchar(A[i][j].v+64);
return 0;
}
