这大概是我这辈子写的最长的ACM代码了，之前写了一道线段数+LCA的题有180多行，以为已经到了极限，没想到这次一写就是280多~不过其中有很多重复部分，删减一下也差不多就一百多行的样子。不管怎么样，发个贴留念下，以后告别ACM不写程序的时候，偶尔拿出来看看，自己奋斗过，疯狂过~
#include<stdio.h>
#include<vector>
#include<string>
#include<iostream>
using namespace std;
struct www
{
string word;
bool used;
};
int w,h,c;
int suc;
char map[16][16];
vector<www> word[16];
bool doublefill[16][16];
int flag;
struct grid
{
int x;
int y;
int len;
vector<int> inter;
};
vector<grid> g[2][16];
bool put(grid a,string b,int dec)
{
int i;
if(dec==0)
{
for(i=0;i<a.inter.size();i++)
if(map[a.x][a.inter[i]]!='#'&&map[a.x][a.inter[i]]!=b[a.inter[i]-a.y])
return false;
}
else
{
for(i=0;i<a.inter.size();i++)
{
int w=a.inter[i];
if(map[a.inter[i]][a.y]!='#'&&map[a.inter[i]][a.y]!=b[a.inter[i]-a.x])
return false;
}
}
return true;
}
void fill(grid a,string b,int dec)
{
int i;
if(dec==0)
for(i=a.y;i<b.length()+a.y;i++)
{
if(map[a.x][i]!='#') doublefill[a.x][i]=1;
map[a.x][i]=b[i-a.y];
}
else
for(i=a.x;i<b.length()+a.x;i++)
{
if(map[i][a.y]!='#') doublefill[i][a.y]=1;
map[i][a.y]=b[i-a.x];
}
}
void unfill(grid a,string b,int dec)
{
int i;
if(dec==0)
{
for(i=a.y;i<b.length()+a.y;i++)
{
if(!doublefill[a.x][i])
map[a.x][i]='#';
doublefill[a.x][i]=0;
}
}
else if(dec==1)
{
for(i=a.x;i<b.length()+a.x;i++)
{
if(!doublefill[i][a.y])
map[i][a.y]='#';
doublefill[i][a.y]=0;
}
}
}
void dfs(int k0,int num0,int k1,int num1,int state)
{
int i,j;
if((k0==1&&flag==1)||(k1==1&&flag==-1))
{
suc=1;
return;
}
if(k0==1)
{
flag=-1;
int z=g[1][k1].size();
if(num1<z-1)
dfs(2,0,k1,num1+1,1);
else
dfs(2,0,k1-1,0,1);
if(suc) return;
}
if(k1==1)
{
flag=1;
int z=g[0][k0].size();
if(num0<z-1)
dfs(k0,num0+1,2,0,0);
else
dfs(k0-1,0,2,0,0);
if(suc) return;
}
if(state==0)
{
if(g[0][k0].size()==0)
{
dfs(k0-1,0,k1,num1,0);
if(suc) return;
}
else
{
for(i=0;i<word[k0].size();i++)
if(!word[k0][i].used&&put(g[0][k0][num0],word[k0][i].word,0))
{
word[k0][i].used=1;
fill(g[0][k0][num0],word[k0][i].word,0);
int z=g[1][k1].size();
if(num1<z-1)
dfs(k0,num0,k1,num1+1,1);
else
dfs(k0,num0,k1-1,0,1);
if(suc) return;
unfill(g[0][k0][num0],word[k0][i].word,0);
word[k0][i].used=0;
}
}
}
else
{
if(g[1][k1].size()==0)
{
dfs(k0,num0,k1-1,num1,1);
if(suc) return;
}
else
{
for(i=0;i<word[k1].size();i++)
if(!word[k1][i].used&&put(g[1][k1][num1],word[k1][i].word,1))
{
word[k1][i].used=1;
fill(g[1][k1][num1],word[k1][i].word,1);
int z=g[0][k0].size();
if(num0<z-1)
dfs(k0,num0+1,k1,num1,0);
else
dfs(k0-1,0,k1,num1,0);
if(suc) return;
unfill(g[1][k1][num1],word[k1][i].word,1);
word[k1][i].used=0;
}
}
}
}
int main()
{
int N;
int i,j,k;
int x,y;
string a;
www ww;
int len,cnt;
struct grid tmp;
freopen("in.txt","r",stdin);
scanf("%d",&N);
for(i=0;i<N;i++)
{
for(j=0;j<16;j++)
word[j].clear();
scanf("%d%d ",&w,&h);
for(j=0;j<h;j++)
gets(map[j]);
scanf("%d",&c);
for(j=0;j<c;j++)
{
cin>>a;
ww.used=0;
ww.word=a;
word[a.length()].push_back(ww);
}
for(j=0;j<16;j++)
{
g[0][j].clear();
g[1][j].clear();
}
tmp.len=0;
for(j=0;j<h;j++)
{
for(k=0;k<w;k++)
{
if(map[j][k]=='.'&&tmp.len!=0)
{
g[0][tmp.len].push_back(tmp);
tmp.len=0;
}
else if(map[j][k]=='#'&&tmp.len==0)
{
tmp.x=j;tmp.y=k;tmp.len=1;
tmp.inter.clear();
if((j>0&&map[j-1][k]=='#')||(j<h-1&&map[j+1][k]=='#'))
tmp.inter.push_back(k);
}
else if(map[j][k]=='#')
{
tmp.len++;
if((j>0&&map[j-1][k]=='#')||(j<h-1&&map[j+1][k]=='#'))
tmp.inter.push_back(k);
}
}
if(tmp.len!=0)
{
g[0][tmp.len].push_back(tmp);
tmp.len=0;
}
}
tmp.len=0;
for(j=0;j<w;j++)
{
for(k=0;k<h;k++)
{
if(map[k][j]=='.'&&tmp.len!=0)
{
g[1][tmp.len].push_back(tmp);
tmp.len=0;
}
else if(map[k][j]=='#'&&tmp.len==0)
{
tmp.x=k;tmp.y=j;tmp.len=1;
tmp.inter.clear();
if((j>0&&map[k][j-1]=='#')||(j<w-1&&map[k][j+1]=='#'))
tmp.inter.push_back(k);
}
else if(map[k][j]=='#')
{
tmp.len++;
if((j>0&&map[k][j-1]=='#')||(j<w-1&&map[k][j+1]=='#'))
tmp.inter.push_back(k);
}
}
if(tmp.len!=0)
{
g[1][tmp.len].push_back(tmp);
tmp.len=0;
}
}
if(w>h) len=w;
else len=h;
for(j=2;j<=len;j++)
if(word[j].size()!=g[0][j].size()+g[1][j].size())
{
suc=0;
break;
}
if(j>len)
{
suc=0;flag=0;
memset(doublefill,0,sizeof(doublefill));
dfs(len,0,len,-1,0);
}
printf("Puzzle #%d\n",i+1);
if(suc)
for(j=0;j<h;j++)
puts(map[j]);
else
printf("I cannot generate this puzzle.\n");
}
return 0;
}
上面这段代码是一个填字游戏，核心就是一个DFS的搜索，我做了很多不是很必须的处理，写的又比较罗嗦，才成就了其不可动摇的长度地位，我把横行和竖行分开了交错填，实在是被数据逼的，因为安长短依次填的话就TLE了，这样可以减小回朔力度。把每串格子记录成起始位置，交错点放置在以长度为下标的vector中，待填字母记录其是否使用过的状态也放在以长度为下标的vector中，这样找的时候就以长度一一对应了，只需判断在交错点处是否有矛盾即可。
留念，撒花，致敬。。。