題目描述

如下的10個(gè)格子，填入0~9的數(shù)字。要求：連續(xù)的兩個(gè)數(shù)字不能相鄰。
（左右、上下、對(duì)角都算相鄰）一共有多少種可能的填數(shù)方案？

image

輸出

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

代碼

又是一道dfs題，因?yàn)槭翘羁疹}如果實(shí)在想不出可用暴搜

#include<bits/stdc++.h>
using namespace std;

int a[4][5],visit[10];
int dx[4]={-1,-1,-1,0};
int dy[4]={0,1,-1,-1};
int sum;

bool check(int x,int y,int n){
    for(int i=0;i<4;i++){
        int xx=x+dx[i];
        int yy=y+dy[i];
        if(xx<3&&xx>=0&&yy>=0&&yy<4){
            if(abs(a[xx][yy]-n)==1)
                return false;
        }
    }
    return true;
}

void dfs(int x,int y){
    if(x==2&&y==3){
        sum++;
        return;
    }
    for(int i=0;i<10;i++){
        if(visit[i]==0&&check(x,y,i)){
            visit[i]=1;
            a[x][y]=i;
            if(y+1<4)
                dfs(x,y+1);
            else
                dfs(x+1,0);//另起一行
            visit[i]=0;
        }
    }
}

int main(){
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
            a[i][j]=-20;
    dfs(0,1);
    cout<<sum;
    return 0;
}