noi1816 画家问题（技巧搜索Dfs）

时间：2021-01-07 07:35:18
/*

Problem 画家问题

假设一个ans数组存的是对每一个点的操作 0表示不图 1表示图

那么 对于原图 g 操作第三行时对第一行没有影响 同样往下类似的

所以 假设我们知道了ans的第一行就是最后答案的第一行 那么对于ans的第二行 就必须是的第一行全变成黄色

以此类推 最后检验第n行 是不是全部黄色就好了

所以只需要枚举第一行的所有情况 共2的n次方种情况

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#define inff 0x7fffffff

using namespace std;

int n,ans[][],g[][],tmp[][],anss,minn=inff,tot;

char s;

void Printf()//计数 染了几个

{

    anss=;

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

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

        if(ans[i][j]==)anss++;

    minn=min(minn,anss);

}

void Pai()//根据ans的第一行 逐行染色

{

    int i,j,f=;

    memset(tmp,,sizeof(tmp));

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

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

        tmp[i][j]=g[i][j];

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

      {

          if(ans[][i]==)

            {

              tmp[][i]=!tmp[][i];

              tmp[][i+]=!tmp[][i+];

              tmp[][i-]=!tmp[][i-];

              tmp[][i]=!tmp[][i];

          }

      }

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

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

        if(tmp[i-][j]==)

          {

            tmp[i-][j]=;

              ans[i][j]=;

              tmp[i][j]=!tmp[i][j];

              tmp[i][j+]=!tmp[i][j+];

              tmp[i][j-]=!tmp[i][j-];

              tmp[i+][j]=!tmp[i+][j];

          }

    for(i=;i<=n;i++)//最后检验最后一行是不是恰好全为黄色

      if(tmp[n][i]==)f=;

    if(f==)Printf();

}

void Dfs(int t)//枚举ans的第一行的所有情况

{

    if(t>n)

      {

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

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

              ans[i][j]=;

          Pai();

        return;

      }

    ans[][t]=;Dfs(t+);

    ans[][t]=;Dfs(t+);

}

int main()

{

    int i,j;

    cin>>n;

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

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

        {

          cin>>s;

          if(s=='w')g[i][j]=;

          else g[i][j]=;

        }

    Dfs();

    if(minn<0x7fffffff)cout<<minn;

    else cout<<"inf";

}

相关文章