搜索

题目链接:搜索一·24点

dfs:

bool zero(double x)
{
    if(fabs(x)<=eps)return true;
    return false;
}

bool equal_24(double a[],int n)
{
    if(n==1)
        if(zero(a[0]-24))return true;
        else return false;
    double b[5];
    for(int i=0; i<n-1; i++)
        for(int j=i+1; j<n; j++)
        {
            int cont=0;
            for(int k=0; k<n; k++)
                if(k!=i&&k!=j)b[cont++]=a[k];

            b[cont]=a[i]+a[j];
            if(equal_24(b,n-1))return true;

            b[cont]=a[i]-a[j];
            if(equal_24(b,n-1))return true;

            b[cont]=a[j]-a[i];
            if(equal_24(b,n-1))return true;

            b[cont]=a[i]*a[j];
            if(equal_24(b,n-1))return true;

            if(!zero(a[j]))
            {
                b[cont]=a[i]/a[j];
                if(equal_24(b,n-1))return true;
            }

            if(!zero(a[i]))
            {
                b[cont]=a[j]/a[i];
                if(equal_24(b,n-1))return true;
            }
        }
    return false;
}

int main()
{
    int T;
    double a[5];
    scanf("%d",&T);
    while(T--)
    {
        for(int i=0; i<4; i++)
            scanf("%lf",&a[i]);
        if(equal_24(a,4))printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

题目链接:搜索二·骑士问题

bfs:

struct point
{
    int x,y,s;
} t;

queue<point>Q;

int step[5][10][10];
const int dx[]= {1,1,-1,-1,2,2,-2,-2};
const int dy[]= {2,-2,2,-2,1,-1,1,-1};
bool vis[10][10];

bool judge(point x)
{
    if(x.x<1||x.x>8)return false;
    if(x.y<1||x.y>8)return false;
    if(vis[x.x][x.y])return false;
    return true;
}

void bfs(int n)
{
    while(!Q.empty())
    {
        point temp=Q.front();
        step[n][temp.x][temp.y]=temp.s;
        Q.pop();
        t.s=temp.s+1;
        for(int i=0; i<8; i++)
        {
            t.x=temp.x+dx[i];
            t.y=temp.y+dy[i];
            if(judge(t))
            {
                vis[t.x][t.y]=true;
                Q.push(t);
            }
        }
    }
}

void init(void)
{
    memset(step,0,sizeof(step));
    while(!Q.empty())Q.pop();
}

int main()
{
    int T;
    char s[5];
    scanf("%d",&T);
    while(T--)
    {
        init();
        for(int i=1; i<=3; i++)
        {
            scanf("%s",s);
            t.x=s[0]-'A'+1;
            t.y=s[1]-'1'+1;
            t.s=0;
            Q.push(t);
            memset(vis,false,sizeof(vis));
            vis[t.x][t.y]=true;
            bfs(i);
        }
        int minn=inf;
        for(int i=1; i<=8; i++)
            for(int j=1; j<=8; j++)
            {
                int res=0;
                for(int k=1;k<=3;k++)
                    res+=step[k][i][j];
                if(res<minn)minn=res;
            }
        printf("%d\n",minn);
    }
    return 0;
}

题目链接:搜索三·八数码问题

bfs:

int fac[9],a[10];

void init(void)
{
    fac[0]=1;
    for(int i=1; i<=8; i++)
        fac[i]=fac[i-1]*i;
}

int cantor(int n)
{
    int res=1;
    for(int i=1; i<=n; i++)
    {
        int t=0;
        for(int j=i+1; j<=n; j++)
            if(a[j]<a[i] && a[j])
                t++;
        if(!a[i])t=n-i;
        res+=t*fac[n-i];
    }
    return res;
}

void uncant(int num,int n)
{
    num--;
    bool vis[10]={0};
    int b[10]= {0};
    for(int i=1; i<=n; i++)
    {
        b[i]=num/fac[n-i];
        num%=fac[n-i];
        int cont=0;
        for(int j=1; j<=n; j++)
            if(!vis[j])
            {
                cont++;
                if(cont==b[i]+1)
                {
                    a[i]=j%9;
                    vis[j]=true;
                    break;
                }
            }
    }
}

bool vis[400000];
int ans[400000];

struct node
{
    int val,s;
    node(int x=0,int y=0):
        val(x),s(y) {}
};

void bfs(void)
{
    queue<node>Q;
    vis[1]=true;
    Q.push(node(1,0));
    while(!Q.empty())
    {
        node temp=Q.front();
        ans[temp.val]=temp.s;
        Q.pop();
        uncant(temp.val,9);
        int zero=0;
        for(int i=1;i<=9;i++)
            if(a[i]==0)zero=i;
        if(zero%3!=1)
        {
            swap(a[zero],a[zero-1]);
            int t=cantor(9);
            if(!vis[t])
            {
                vis[t]=true;
                Q.push(node(t,temp.s+1));
            }
            swap(a[zero],a[zero-1]);
        }

        if(zero%3!=0)
        {
            swap(a[zero],a[zero+1]);
            int t=cantor(9);
            if(!vis[t])
            {
                vis[t]=true;
                Q.push(node(t,temp.s+1));
            }
            swap(a[zero],a[zero+1]);
        }

        if(zero>3)
        {
            swap(a[zero],a[zero-3]);
            int t=cantor(9);
            if(!vis[t])
            {
                vis[t]=true;
                Q.push(node(t,temp.s+1));
            }
            swap(a[zero],a[zero-3]);
        }

        if(zero<7)
        {
            swap(a[zero],a[zero+3]);
            int t=cantor(9);
            if(!vis[t])
            {
                vis[t]=true;
                Q.push(node(t,temp.s+1));
            }
            swap(a[zero],a[zero-3]);
        }
    }
}

int main()
{
    memset(ans,-1,sizeof(ans));
    init();
    bfs();
    int T;
    scanf("%d",&T);
    while(T--)
    {
        for(int i=1;i<=9;i++)
            scanf("%d",&a[i]);
        int res=ans[cantor(9)];
        if(res==-1)printf("No Solution!\n");
        else printf("%d\n",res);
    }
    return 0;
}