求助帖。。。不知道这个算法错在哪里了。。
#include <string.h>#include "iostream.h"
#include <stdio.h>
#include <fstream.h>
//=======================================
//结构体
typedef unsigned char BYTE;
typedef struct{
BYTE aa[5][5];
}pp;
//===============================================
//构造基本图形
BYTE pc00[5][5]={{1,1,1},{1},{1}};
BYTE pc01[5][5]={{2,2},{2},{2,2}};
BYTE pc02[5][5]={{3,3},{3,3},{3}};
BYTE pc03[5][5]={{4,4},{4},{4},{4}};
BYTE pc04[5][5]={{5},{5,5},{0,5},{0,5}};
BYTE pc05[5][5]={{6},{6,6},{6},{6}};
BYTE pc06[5][5]={{7,7,7},{0,7},{0,7}};
BYTE pc07[5][5]={{0,8},{8,8,8},{0,8}};
BYTE pc08[5][5]={{0,9},{9,9},{0,9,9}};
BYTE pc09[5][5]={{10,10,10,10,10}};
BYTE pc10[5][5]={{0,11,11},{11,11},{11}};
BYTE pc11[5][5]={{12,12},{0,12},{0,12,12}};
pp* orig[]={
(pp*)pc00,
(pp*)pc01,
(pp*)pc02,
(pp*)pc03,
(pp*)pc04,
(pp*)pc05,
(pp*)pc06,
(pp*)pc07,
(pp*)pc08,
(pp*)pc09,
(pp*)pc10,
(pp*)pc11,
};
typedef struct{
BYTE poa[60];
BYTE mark[12];
}fboard;
//==================================================
//全局变量
pp var[12][8];
int nvar[12];
int brow=0,bcol=0;
int flg=-1;
//==================================================
//计算数组下标函数
int addr(int row,int col){
return(row-1)*bcol+col-1;
}
//==================================================
//旋转函数
void rotp(pp* des,pp* src){
memset(des,0,sizeof(pp));
for(int x=4,flag=0,xp=0;x>=0;x--){
for(int y=0;y<5;y++){
des->aa[xp][y]=src->aa[y][x];
if(src->aa[y][x])flag=1;
}
if(flag)xp++;
}
cout<<"rotp"<<endl;
}
//===================================================
//翻转函数
void flip(pp* des,pp* src){
memset(des,0,sizeof(pp));
for(int x=4,flag=0,xp=0;x>=0;x--){
for(int y=0;y<=5;y++){
des->aa[y][xp]=src->aa[y][x];
if(src->aa[y][x])flag=1;
}
if(flag)xp++;
}
cout<<"flip"<<endl;
}
//=====================================================
//初始化数组
void init(){
pp tmp1,tmp2;
for(int b=0;b<12;b++){
tmp1=*orig[b];
int d;
int vc=0;
for( d=0;d<5;d++)
for(int c=0;c<5;c++)
if(tmp1.aa[d][c])tmp1.aa[d][c]|=0x10;
for(int a=0;a<8;a++){
int exist=0,c;
for(c=0;c<vc&&!exist;c++)
if(memcmp(&var[b][c],&tmp1,sizeof(pp))==0)exist=1;
if(!exist) var[b][vc++]=tmp1;//旋转
tmp2=tmp1;rotp(&tmp1,&tmp2);//翻转
if(a==3){tmp2=tmp1;flip(&tmp1,&tmp2);}
}
nvar[b]=vc;
}
cout<<"init"<<endl;
}
//=======================================================
//检测图形是否覆盖完全函数
bool check(pp* tryp,fboard *ff,int px,int py){
for(int row=0;row<5;row++)
for(int col=0;col<5;col++)
if(tryp->aa[row][col]){
int r=row+py,c=col+px;
if(r>brow||c>bcol||ff->poa[addr(r,c)])return 0;
}
return 1;
cout<<"check"<<endl;
}
//=======================================================
//输出函数
void outf(fboard *ff)
{
if(flg){
for(int col=1;col<=bcol;col++){
for(int row=1;row<=brow;row++){
int x=ff->poa[addr(row,col)]-16;
if(x<10)cout<<x;
if(x==10)cout<<"a";
if(x==11)cout<<"b";
if(x==12)cout<<"c";
}
cout<<endl;
}
}
else{
for(int row=1;row<=brow;row++){
for(int col=1;col<=bcol;col++){
int x=ff->poa[addr(row,col)]-16;
if(x<10)cout<<x;
if(x==10)cout<<"a";
if(x==11)cout<<"b";
if(x==12)cout<<"c";
}
cout<<endl;
}
}
cout<<"outf"<<endl;
}
//======================================================
//回溯搜索函数
void search(fboard *pre){
int ans=0;
int npla=0,frow=0,fcol=0;
fboard ff=*pre;
if(ans>0) return;
//找最左上的未覆盖方格
for(int row=1,found=0;row<=brow&&!found;row++)
for(int col=1;col<=bcol&&!found;col++)
if(pre->poa[addr(row,col)]==0){
frow=row;fcol=col;found=1;
}
//计算已经用过的图形数
int pn;
for(pn=0;pn<12;pn++)if(pre->mark[pn]) npla++ ;
for(pn=0;pn<12;pn++){
//是否用过
if(pre->mark[pn])continue;
//每种不同形态
for(int pv=0;pv<nvar[pn];pv++){
pp tryp=var[pn][pv];
int py=frow;
for(int px=1;px<=bcol;px++){
if(px>fcol)break;
if(check(&tryp,&ff,px,py)){
//用该图形覆盖一下
for(int row=0;row<5;row++){
for(int col=0;col<5;col++){
ff.poa[addr(row+py,col+px)]=tryp.aa[row][col];
}
}
ff.mark[pn]=1;
if(npla>10){++ans;outf(&ff);return;}
else search(&ff);
//回溯
ff=*pre;
}//if
}//px
}//pv
}//pn
cout<<"search"<<endl;
}
//============================================================
//主函数
int main()
{
cin>>brow>>bcol;
if(brow<bcol){int tmp=brow;brow=bcol;bcol=tmp;flg=1;}
if(bcol<3||brow*bcol!=60)cout<<"No Solution!"<<endl;
else{
init();
fboard ff;
memset(&ff,0,sizeof(fboard));
search(&ff);
}
return 0;
}
正确的输入输出结果：~~~~~~~~~~~~~~~~~~~~~~~~
input.txt output.txt
6 10 111c9aaaaa
1ccc999777
1c3339bb74
22233bb874
26255b8884
6666555844
