codevs 2495 水叮当的舞步IDA*

时间：2021-10-20 18:47:02
/*

比较简单的A* 估价函数很简单就是除了左上角的联通快之外的不同的个数

加上迭代 好像答案最多在16步之内出解

这样裸裸的交上去是50分

在考虑剪枝 每个选颜色的时候一定是选左上角联通快附近的颜色

处理一下只枚举这样的颜色 80 - 90 分了就

下面是代码

*/

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int n,ans,g[][],a[][],tot,color,falg,f[][],vis[],C;

int xx[]={,,-,};

int yy[]={,-,,};

int init()

{

    int x=;char s=getchar();

    while(s<''||s>'')s=getchar();

    while(s>=''&&s<=''){x=x*+s-'';s=getchar();}

    return x;

}

void Go(int x,int y,int c,int r)

{

    a[x][y]=r;f[x][y]=;

    for(int i=;i<;i++)

      {

          int nx=x+xx[i];

          int ny=y+yy[i];

          if(nx>&&nx<=n&&ny>&&ny<=n&&f[nx][ny]==&&a[nx][ny]==c)

            Go(nx,ny,c,r);

      }

}

void Get_round(int x,int y,int c,int round[])

{

    f[x][y]=;

    for(int i=;i<;i++)

      {

          int nx=x+xx[i];

          int ny=y+yy[i];

          if(nx>&&nx<=n&&ny>&&ny<=n&&f[nx][ny]==)

            {

                if(a[nx][ny]==c)Get_round(nx,ny,c,round);

                else if(round[a[nx][ny]]==)round[a[nx][ny]]=;

          }

      }

}

void Dfs(int now,int sum)

{

    if(falg)return;

    memset(vis,,sizeof(vis));C=;

    for(int i=;i<=n;i++)for(int j=;j<=n;j++)if(vis[a[i][j]]==){vis[a[i][j]]=;C++;}

    if(now==sum)

      {

          if(C==)falg=;

          return;

      }

    if(now+C->sum)return;

    memset(f,,sizeof(f));

    int round[];memset(round,,sizeof(round));

    Get_round(,,a[][],round);

    for(int i=;i<=;i++)

      {

          if(i==a[][]||round[i]==)continue;

          int back[][];

        memcpy(back,a,sizeof(a));

          memset(f,,sizeof(f));

        Go(,,a[][],i);

        Dfs(now+,sum);if(falg)return;

          memcpy(a,back,sizeof(back));

      }

}

int main()

{

    while()

      {

          n=init();if(n==)break;

          for(int i=;i<=n;i++)

            for(int j=;j<=n;j++)

              g[i][j]=init();

          for(int k=;k<=;k++)

            {

                memcpy(a,g,sizeof(g));

                falg=;Dfs(,k);

                if(falg)

                  {

                      ans=k;break;

              }

          }

        printf("%d\n",ans);

      }

    return ;

}
/*

只像上面那样好像A不了 （也可能是我常数太大了QAQ...）

最后没办法了 看了题解

每次灌水的时候似乎很慢

我们处理f数组 1表示已经在左上角 2表示在左上角的周围

这样不灌水 同样的处理了这个问题

虽然过了 但还是跑的比较慢.....

*/

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int n,ans,g[][],tot,color,falg,f[][],vis[],C;

int xx[]={,,-,};

int yy[]={,-,,};

int init()

{

    int x=;char s=getchar();

    while(s<''||s>'')s=getchar();

    while(s>=''&&s<=''){x=x*+s-'';s=getchar();}

    return x;

}

void dfs(int x,int y,int r)

{

    f[x][y]=;

    for(int i=;i<;i++)

      {

          int nx=x+xx[i];

          int ny=y+yy[i];

          if(nx>&&nx<=n&&ny>&&ny<=n&&f[nx][ny]==)

            {

                if(g[nx][ny]==r)dfs(nx,ny,r);

            else f[nx][ny]=;

          }

      }

}

bool Go(int r)

{

    int ret=;

    for(int i=;i<=n;i++)

      for(int j=;j<=n;j++)

        if(f[i][j]==&&g[i][j]==r)

          ret=,dfs(i,j,r);

    return ret;

}

void Dfs(int now,int sum)

{

    if(falg)return;

    memset(vis,,sizeof(vis));C=;

    for(int i=;i<=n;i++)

      for(int j=;j<=n;j++)

        if(vis[g[i][j]]==&&f[i][j]!=)

          vis[g[i][j]]=,C++;

    if(now==sum)

      {

          if(C==)falg=;

        return;

      }

    if(now+C->sum)return;

    int back[][];

    memcpy(back,f,sizeof(f));

    for(int i=;i<=;i++)

      {

        if(Go(i))Dfs(now+,sum);

        if(falg)return;

          memcpy(f,back,sizeof(back));

      }

}

int main()

{

    while()

      {

          n=init();if(n==)break;

          memset(f,,sizeof(f));

          for(int i=;i<=n;i++)

            for(int j=;j<=n;j++)

              g[i][j]=init();

          dfs(,,g[][]);

          for(int k=;k<=;k++)

            {

                falg=;Dfs(,k);

                if(falg){ans=k;break;}

          }

        printf("%d\n",ans);

      }

    return ;

}

相关文章