kb-01-d<poj3279>--深搜变种，二进制优化；

poj--3279

题意：

给n*m的矩阵，0 1组成，每次翻转一个格子可以将上下左右的五个节点翻转，求，把所有的格子翻转成0；输出每个个字的翻转次数；最少字数；

做法：

从上到下，第一行翻转的情况确定的话就全确定了；因此只要枚举第一行的翻转情况就可以了；

第一行翻转0次或1次；所以可以用二进制化，不用dfs了；具体看代码实现；

对于每一种第一行看需要翻转的次数是否是最小的；

代码如此：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #define inf 0x3f3f3f3f

 using namespace std;

 int n,m,ans;

 int a[][],vis[][]={},t[][]={},p[][]={,,,,,-,,,-,},an[][]={};

 bool s[];      //vis数组用来记录主动翻转的情况；t数组用来记录一共翻转的次数；an数组用来记录最终结果；

 int solve()         //根据第一行的情况确定剩余所有行的情况；

 {

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

     {

         if(vis[][i]==)

         {

             t[][i]++;

             if(n>)

             t[][i]++;

             if(i<m-)

             t[][i+]++;

             if(i>)

             t[][i-]++;

         }

     }

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

     {

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

         {

             if(t[i-][j]%!=a[i-][j])

             {

                 vis[i][j]=;

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

                 {

                     int x=i+p[z][],y=j+p[z][];

                     t[x][y]++;

                 }

             }

         }

     }

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

     {

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

         {

             if(t[i][j]%!=a[i][j])

                 return ;

         }

     }

     return ;

 }

 int main()

 {

     while(cin>>n>>m)

     {

         memset(a,,sizeof(a));

         memset(vis,,sizeof(vis));

         memset(t,,sizeof(t));

         ans=inf;

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

         {

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

             {

                 scanf("%d",&a[i][j]);

             }

         }

        for(int i=;i<pow(2.0,m);i++)

        {

            memset(vis,,sizeof(vis));

            for(int j=m-;j>=;j--)

            {

                s[j]=i&(<<j);

                vis[][j]=s[j];

            }

            memset(t,,sizeof(t));

            int temp=solve(),cou=;

            if(temp==)

            {

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

                {

                    for(int j=m-;j>=;j--)

                    {

                        if(vis[i][j]==)

                             cou++;

                    }

                }

                if(cou<ans)

                {

                    ans=cou;

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

                    {

                        for(int j=m-;j>=;j--)

                            an[i][j]=vis[i][j];

                    }

                }

            }

        }

        if(ans!=inf)

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

            {

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

                {

                    if(j!=)

                        printf(" ");

                    printf("%d",an[i][j]);

                }

                printf("\n");

            }

        else

            printf("IMPOSSIBLE\n");

     }

     return ;

 }

巴特西

kb-01-d<poj3279>--深搜变种，二进制优化；

最新文章

热门文章