曹利国讲的搜素例题。
结果又被虐爆了........
当时上课时貌似还是我想出了连通块的剪枝，实现起来却一塌糊涂。
果然我弱得会被任意一道搜索题虐爆。
一直在压常数，最后改成了这个非常简洁的代码。
但问题不在这里
一开始把
if(x==n&&y==1){
if(i==n*n)
count++;
return ;
}
写成了
if(i==n*n){
if(x==n&&y==1)
count++;
return ;
}
这个错误足以使之超时
——这里会走完所有 遍历所有点的走法
而事实上只需走完所有 从1,1到n,1的路径即可
更严重的问题是考虑联通块时，没有考虑边界的情况。
事实上只需把外边框标记为已走过就行了。
代码
#include<cstdio>
#include<cstring>
#include<cstdlib>
int count=0;
int n;
void dfs(int x,int y,int i);
bool a[15][15];
int main()
{
freopen("betsy.in","r",stdin);
freopen("betsy.out","w",stdout);
scanf("%d",&n);
memset(a,true,sizeof(a));
for(int i=1;i<=n;i++)
a[i][0]=a[i][n+1]=a[0][i]=a[n+1][i]=false;
dfs(1,1,1);
printf("%d\n",count);
fclose(stdin);
fclose(stdout);
return 0;
}
void dfs(int x,int y,int i){
if(x==n&&y==1){
if(i==n*n)
count++;
return ;
}
if((!a[x+1][y+1]&&a[x+1][y]&&a[x][y+1])
||(!a[x-1][y-1]&&a[x-1][y]&&a[x][y-1])
||(!a[x-1][y+1]&&a[x-1][y]&&a[x][y+1])
||(!a[x+1][y-1]&&a[x+1][y]&&a[x][y-1])
||(a[x+1][y]&&a[x-1][y]&&!a[x][y-1]&&!a[x][y+1])
||(!a[x+1][y]&&!a[x-1][y]&&a[x][y-1]&&a[x][y+1])
)
return ;
a[x][y]^=true;
if(a[x][y+1])
dfs(x,y+1,i+1);
if(a[x][y-1])
dfs(x,y-1,i+1);
if(a[x+1][y])
dfs(x+1,y,i+1);
if(a[x-1][y])
dfs(x-1,y,i+1);
a[x][y]^=true;
}