7-10 守卫棋盘 uva11214

输入要给n*m的棋盘均小于10 某些格子有标记用最少的皇后辐射到所有的标记

限时 6666ms

用IDA* 时间6000 尴尬。

#include<bits/stdc++.h>

using namespace std;

#define N 10

int n,m;

int mp[N][N];

int cnt;

int visn[N];

int vism[N];

int visx[*N];

bool dfs(int d,int maxx)

{

    if(cnt==)return true;

    if(d==maxx)return false;

    if( (maxx-d)*( *n+m-  )  <cnt )return false;//毫无用处。。

    int oldmap[N][N];//一定要开到里面  一开始开到外面错了！

    memcpy(oldmap,mp,sizeof mp);

    int oldcnt=cnt;

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

        if(!visn[i])

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

        if(!vism[j])

      {

          visn[i]=vism[j]=visx[i+j]=;

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

             if(mp[k][j])cnt--,mp[k][j]=;

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

              if(mp[i][k])cnt--,mp[i][k]=;

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

            for(int s=;s<=m;s++)

           {

               if( (s-k)==(j-i)||(s+k)==(i+j) )

                if(mp[k][s]) mp[k][s]=,cnt--;

           }

            if(cnt!=oldcnt)

            if(dfs(d+,maxx))return true;

          memcpy(mp,oldmap,sizeof mp);

          cnt=oldcnt;

          visn[i]=vism[j]=;

      }

  return false;

}

int solve()

{

    if(cnt==)return ;

     for(int maxx=;;maxx++){

        memset(visn,,sizeof visn);

        memset(vism,,sizeof vism);

        if(dfs(,maxx) )return maxx;

     }

}

int main()

{

    int cas=;

    while(scanf("%d",&n),n)

    {    cnt=;

        scanf("%d",&m);getchar();

        char ch;

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

        {

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

        {

            scanf("%c",&ch);

            if(ch=='X')mp[i][j]=,cnt++;

        }

        getchar();

        }

        printf("Case %d: %d\n",++cas,solve());

    }

}

每次dfs都要扫面落子的四个方位实在太费时间真的铁脑残

应该像八皇后问题那样设置标记数组就好了！！ 900ms

#include<bits/stdc++.h>

using namespace std;

#define N 10

int n,m;

int mp[N][N];

int cnt;

int visn[N];

int vism[N];

int visx[*N];

int visy[*N];

bool judge()

{

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

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

            if(mp[i][j]&&!visn[i]&&!vism[j]&&!visx[i+j]&&!visy[i-j+])return false;

    return true;

}

bool dfs(int d,int maxx)

{

    if(judge())return true;

    if(d==maxx)return false;

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

        if(!visn[i])

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

        if(!vism[j])

      {

          visn[i]=vism[j]=;

          int a=visx[i+j], b=visy[i-j+];

          visx[i+j]=visy[i-j+]=;

            if(dfs(d+,maxx))return true;

          visn[i]=vism[j]=;

          visx[i+j]=a;visy[i-j+]=b;

      }

  return false;

}

int solve()

{

    if(cnt==)return ;

     for(int maxx=;;maxx++){

        memset(visn,,sizeof visn);

        memset(vism,,sizeof vism);

        memset(visx,,sizeof visx);

        memset(visy,,sizeof visy);

        if(dfs(,maxx) )return maxx;

     }

}

int main()

{

    int cas=;

    while(scanf("%d",&n),n)

    {    cnt=;

        scanf("%d",&m);getchar();

        char ch;

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

        {

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

        {

            scanf("%c",&ch);

            if(ch=='X')mp[i][j]=,cnt++;

            else mp[i][j]=;

        }

        getchar();

        }

        printf("Case %d: %d\n",++cas,solve());

    }

}

对行数进行优化使行数升序：90ms 可以保证没有重复！！！上面那个代码有很多重复

#include<bits/stdc++.h>

using namespace std;

#define N 10

#define maxn 12

int n,m;

int mp[N][N];

int cnt;

int visn[N];

int vism[N];

int visx[*N];

int visy[*N];

int maxx;

bool judge()

{

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

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

            if(mp[i][j]&&!visn[i]&&!vism[j]&&!visx[i+j]&&!visy[i-j+])return false;

    return true;

}

bool dfs(int d,int raw)

{

    if(judge())return true;

    if(d==maxx)return false;

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

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

      {

          int c=visn[i],d1=vism[j],a=visx[i+j], b=visy[i-j+];

          visx[i+j]=visy[i-j+]=visn[i]=vism[j]=;

            if(dfs(d+,i+))return true;

          visn[i]=c,vism[j]=d1;

          visx[i+j]=a;visy[i-j+]=b;

      }

  return false;

}

int solve()

{

     for( maxx=;;maxx++){

        memset(visn,,sizeof visn);

        memset(vism,,sizeof vism);

        memset(visx,,sizeof visx);

        memset(visy,,sizeof visy);

        if(dfs(,) )return maxx;

     }

}

int main()

{

    int cas=;

    while(scanf("%d",&n),n)

    {

        scanf("%d",&m);getchar();

        char ch;

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

        {

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

        {

            scanf("%c",&ch);

            if(ch=='X')mp[i][j]=;

            else mp[i][j]=;

        }

        getchar();

        }

        printf("Case %d: %d\n",++cas,solve());

    }

}

巴特西

7-10 守卫棋盘 uva11214

最新文章

热门文章