曹利國講的搜素例題。
結果又被虐爆了........
當時上課時貌似還是我想出了連通塊的剪枝，實現(xiàn)起來卻一塌糊涂。
果然我弱得會被任意一道搜索題虐爆。
一直在壓常數(shù)，最后改成了這個非常簡潔的代碼。
但問題不在這里
一開始把
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的路徑即可
更嚴重的問題是考慮聯(lián)通塊時，沒有考慮邊界的情況。
事實上只需把外邊框標記為已走過就行了。
代碼
#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;
}