如下的10個格子（圖片在壓縮文件里）
填入0~9的數(shù)字。要求：連續(xù)的兩個數(shù)字不能相鄰。
（左右、上下、對角都算相鄰）

一共有多少種可能的填數(shù)方案？

請?zhí)顚懕硎痉桨笖?shù)目的整數(shù)。

思路：這道題目其實思路蠻多的。最常規(guī)的就是全排列之后判斷是否符合條件。但是那樣判斷條件特別多，容易遺漏或者寫錯。用dfs好寫一些，并且判斷條件少。將格子看作是一個3行4列的迷宮，從（1,2)開始走到（3，4）結(jié)束。每次填空的時候判斷一下是否符合條件就可以了。
代碼如下：

#include<bits/stdc++.h> #define ll long long using namespace std;const int maxx=11; int d[][2]={{1,0},{0,1},{-1,0},{0,-1},{1,1},{-1,1},{1,-1},{-1,-1}}; bool vis[maxx]; int f[maxx][maxx]; int ans=0;inline void dfs(int x,int y) {if(x==3&&y==4){ans++;return ;}if(y==5){dfs(x+1,1);return ;}for(int i=0;i<=9;i++){if(vis[i]==0){int flag=1;for(int k=0;k<8;k++){int tx=x+d[k][0];int ty=y+d[k][1];if(f[tx][ty]==-1) continue;if(abs(f[tx][ty]-i)==1) {flag=0;break;}}if(flag) {f[x][y]=i;vis[i]=1;dfs(x,y+1);f[x][y]=-1;vis[i]=0;}}} } int main() {memset(vis,0,sizeof(vis));memset(f,-1,sizeof(f));ans=0;dfs(1,2);cout<<ans<<endl; }

答案是1580.
努力加油a啊

總結(jié)

以上是生活随笔為你收集整理的16年蓝桥杯省赛-方格填数（dfs+回溯）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。