蓝桥杯--方格填数

古城微笑少年丶 2022-05-28 02:26 188阅读 0赞

方格填数  
如下的10个格子  
   +--+--+--+  
   |  |  |  |  
\+--+--+--+--+  
|  |  |  |  |  
\+--+--+--+--+  
|  |  |  |  
\+--+--+--+  
  
  
（如果显示有问题，也可以参看【图1.jpg】）  
  
  
填入0~9的数字。要求：连续的两个数字不能相邻。  
（左右、上下、对角都算相邻）  
  
  
一共有多少种可能的填数方案？  
  
  
请填写表示方案数目的整数。

注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

#include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    
    int num[3][4],sum;
    int vis[10];
    int dx[]= {-1,-1,0,-1};
    int dy[]= {0,1,-1,-1};
    int A(int x,int y)//判断它的正上方，右上方，左上方,正左方四个方向即可
    {
        for(int i=0; i<4; i++)
        {
            int xx=x+dx[i];
            int yy=y+dy[i];
            if(xx<0||xx>2||yy<0||yy>3||num[xx][yy]==-1)//超出范围的不算,第一个和最后一个格子不用算
                continue;
            else if(abs(num[xx][yy]-num[x][y])==1)//如果相差为1，即表示相邻
            {
                return 0;
            }
        }
        return 1;
    }
    
    void dfs(int step)
    {
        int x=step/4;
        int y=step%4;
    
        if(step>10)
        {
            int ok=0;
            for(int i=0; i<3; i++)
            {
                for(int j=0; j<4; j++)
                {
                    if((i==0&&j==0)||(i==2&&j==3))
                        continue;
                    if(!A(i,j))
                    {
                        ok=1;
                        break;
                    }
                }
                if(ok)
                    break;
            }
            if(!ok)
            {
                sum++;
    //            for(int i=0; i<3; i++)
    //            {
    //                for(int j=0; j<4; j++)
    //                {
    //                    printf("%d",num[i][j]);
    //                }
    //                printf("\n");
    //            }
    //            printf("\n");
            }
            return ;
        }
        for(int i=0; i<10; i++)
        {
            //num[x][y]=i;
            if(!vis[i])//没有用过i这个数
            {
                num[x][y]=i;
                vis[i]=1;
                dfs(step+1);
                vis[i]=0;
            }
        }
    }
    int main()
    {
        memset(num,-1,sizeof(num));//初始化全为-1,方便处理第一个和最后一个格子
        sum=0;
        dfs(1);
        printf("%d\n",sum);
        return 0;
    }

还可以这样写

#include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    
    int num[3][4],sum;
    int vis[10];
    int dx[]= {-1,-1,0,-1};
    int dy[]= {0,1,-1,-1};
    int A(int x,int y)//判断它的正上方，右上方，左上方,正左方四个方向即可
    {
        for(int i=0; i<4; i++)
        {
            int xx=x+dx[i];
            int yy=y+dy[i];
            if(xx<0||xx>2||yy<0||yy>3||num[xx][yy]==-1)//超出范围的不算,第一个和最后一个格子不用算
                continue;
            else if(abs(num[xx][yy]-num[x][y])==1)//如果相差为1，即表示相邻
            {
                return 0;
            }
        }
        return 1;
    }
    void dfs(int step)
    {
        int x=step/4;
        int y=step%4;
    
        if(step>10)
        {
            sum++;
    //        for(int i=0; i<3; i++)
    //        {
    //            for(int j=0; j<4; j++)
    //            {
    //                printf("%d",num[i][j]);
    //            }
    //            printf("\n");
    //        }
            return ;
        }
        for(int i=0; i<10; i++)
        {
            num[x][y]=i;//先填一个数
            if(!vis[i]&&A(x,y))//然后判断填的这个数是不是和前面的数不相邻
            //不相邻再递归填下一个数,直至找到一种复合的情况，在回溯去找另一种复合的情况,和八皇后思路一样
            {
                vis[i]=1;
                dfs(step+1);
                vis[i]=0;
            }
        }
    }
    int main()
    {
        memset(num,-1,sizeof(num));//初始化全为-1,方便处理第一个和最后一个格子
        sum=0;
        dfs(1);
        printf("%d\n",sum);
        return 0;
    }