ickchen2

PKU3702 搜索

/*很好的一道搜索题,利用了统计的方法,使状态数减少*/
#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
#define M 10000
using namespace std;
int a[4];
int b[4];
int v[M];
int ans;
int que[M];
string s1,s2;
void init(int *a,int *b)
{
    for(int i=0;i<4;i++)
    {
        a[i]=b[i];
    }
}
bool bfs()
{
    memset(v,0,sizeof(v));
    int t=0;
    for(int i=0;i<4;i++)
    {
        t=t*10+a[i];
    }
    int tail=0,head=0;
    que[tail++]=t;
    v[t]=1;
    while(head<tail)
    {
        int k=que[head++];
        for(int i=3;i>=0;--i)
        {
            a[i]=k%10;
            k/=10;
            b[i]=a[i];
        }
        for(int i=0;i<4;i++)
        {
            init(a,b);
            if(a[i]&&a[(i+2)%4]&&a[(i+1)%4]<8&&a[(i+3)%4]<8)
            {
                a[i]--;
                a[(i+1)%4]++;
                a[(i+2)%4]--;
                a[(i+3)%4]++;
            }
            int t=0;
            for(int j=0;j<4;j++)
            {
                t=t*10+a[j];
            }
            if(!v[t]){v[t]=1;que[tail++]=t;if(t==ans)return true;}
            init(a,b);
            if(a[i]&&a[(i+1)%4]&&a[(i+2)%4]<8)
            {
                a[i]--;
                a[(i+1)%4]--;
                a[(i+2)%4]++;
            }
            t=0;
            for(int j=0;j<4;j++)
            {
                t=t*10+a[j];
            }
            if(!v[t]){v[t]=1;que[tail++]=t;if(t==ans)return true;}
        }
    }
    return false;
}
int main()
{
    freopen("3702.txt","r",stdin);
    int ca;
    scanf("%d",&ca);
    while(ca--)
    {
        cin>>s1>>s2;
        memset(a,0,sizeof(a));
  memset(b,0,sizeof(b));
        int t=0;
        for(int i=0;i<s1.size();i++)
        {
           if(s1[i]=='*')a[i%4]++;
        }
        for(int i=0;i<s2.size();i++)
        {
           if(s2[i]=='*')b[i%4]++;
        }
        ans=0;
        for(int i=0;i<4;i++)
        {
            ans=ans*10+b[i];
            t=t*10+a[i];
        }
        if(t==ans)printf("YES\n");
        else
        printf("%s\n",bfs()?"YES":"NO");
    }
}

posted on 2008-10-06 12:51 神之子 阅读(162) 评论(0)  编辑 收藏 引用 所属分类: PKU月赛


只有注册用户登录后才能发表评论。
相关文章:
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年4月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

导航

统计

常用链接

留言簿(1)

随笔分类

随笔档案

文章分类

文章档案

搜索

最新评论

阅读排行榜

评论排行榜