我是先找出所有0点，然后计算每个0点的能取状态数，最后按状态数排序，从状态数最小的0点开始深搜，不知道为什么一直超时
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
int b[9][9];
int nx[100],ny[100],top,n[100],r[100];//top表示有多少个0，n表示每个0点可放数的数目，nx表示每个0点的横坐标，ny表示纵坐标，r用来对所有0点的状态数排序
int cmp(const int i,const int j)
{
    return n[i]<n[j];
}
int judge(int x,int y,int num)
{
    int i,j;
    for(i=0;i<9;i++)
        if(b[i][y]==num) return 0;
    for(i=0;i<9;i++)
        if(b[x][i]==num) return 0;
    for(i=x/3*3;i<=x/3*3+2;i++)
        for(j=y/3*3;j<=y/3*3+2;j++)
            if(b[i][j]==num) return 0;
    return 1;
}
int count(int x,int y)
{
    int num=0,temp=1;
    while(temp<10)
    {
        if(judge(x,y,temp)) num++;
        temp++;
    }
    return num;
}
int dfs(int k)
{
    if(k==top) return 1;
    int e=r[k];
    int i;
    for(i=1;i<=9;i++)
    {
        if(!judge(nx[e],ny[e],i)) continue;
        int x=nx[e],y=ny[e];
        b[x][y]=i;
        if(dfs(k+1)) return 1;
        b[x][y]=0;
    }
    return 0;
}
int main()
{
    int i,j,t;
    char s[11];
    scanf("%d",&t);
    while(t--)
    {
        top=0;
        for(i=0;i<9;i++)
        {
            scanf("%s",s);
            for(j=0;j<9;j++)
            {
                b[i][j]=s[j]-'0';
                if(b[i][j]==0)
                {
                    nx[top]=i;
                    ny[top]=j;
                    n[top]=count(nx[top],ny[top]);
                    r[top]=top;
                    top++;
                }
            }
        }
        sort(r,r+top,cmp);
        dfs(0);
        for(i=0;i<9;i++)
        {
            for(j=0;j<9;j++)
                printf("%d",b[i][j]);
            printf("\n");
        }
    }
    return 0;
}

• Re:用了剪枝还是超时，求大牛帮我一下~~~ (1956) L1328394661 2015-07-29 09:57:08