第七届C/C++B-方格填数

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

思路：

DFS

优化：

因为搜索的位置是按照很纵坐标依次增大来的，所以原来设定的8个方向就可以缩短为4个方向。

测试结果：1580

代码：

#include<iostream>#include<cstdio>#include<string>#include<cstring>#include<cmath>using namespace std;int ans[3][4];bool bns[10];int dir[8][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};int sum=0;void init(){    memset(ans,-1,sizeof(ans));    memset(bns,false,sizeof(bns));}bool check(int x, int y, int num){    int sx,sy;    for(int i=0;i<=7;i++)    {        sx=x+dir[i][0];        sy=y+dir[i][1];        if(sx<0||sx>2||sy<0||sy>3)//越界跳过            continue;        if(ans[sx][sy]==-1)            continue;        if(fabs(ans[sx][sy]-num)==1)            return false;    }    return true;}void dfs(int x, int y)//位置的横坐标、纵坐标{    for(int i=0;i<=9;i++)    {        if(!bns[i]&&check(x,y,i))//没有使用过i，并且检查可用        {            bns[i]=true;            ans[x][y]=i;            if(x==2&&y==2)            {                sum++;            }            else            {                if(y!=3)                    dfs(x,y+1);                else                {                    dfs(x+1,0);                }            }            bns[i]=false;            ans[x][y]=-1;        }    }}int main(){    init();    dfs(0,1);    PRintf("%d/n",sum);//1580    return 0;}优化之后：
#include<iostream>#include<cstdio>#include<string>#include<cstring>#include<cmath>using namespace std;int ans[3][4];bool bns[10];int dir[4][2]={{-1,-1},{-1,0},{-1,1},{0,-1}};int sum=0;void init(){    memset(ans,-1,sizeof(ans));    memset(bns,false,sizeof(bns));}bool check(int x, int y, int num){    int sx,sy;    for(int i=0;i<=3;i++)    {        sx=x+dir[i][0];        sy=y+dir[i][1];        if(sx<0||sx>2||sy<0||sy>3)//越界跳过            continue;        if(ans[sx][sy]==-1)            continue;        if(fabs(ans[sx][sy]-num)==1)            return false;    }    return true;}void dfs(int x, int y)//位置的横坐标、纵坐标{    for(int i=0;i<=9;i++)    {        if(!bns[i]&&check(x,y,i))//没有使用过i，并且检查可用        {            bns[i]=true;            ans[x][y]=i;            if(x==2&&y==2)            {                sum++;            }            else            {                if(y!=3)                    dfs(x,y+1);                else                {                    dfs(x+1,0);                }            }            bns[i]=false;            ans[x][y]=-1;//优化之后这里就不用恢复现场也可以        }    }}int main(){    init();    dfs(0,1);    printf("%d/n",sum);//1580    return 0;}