【搜索】Fliptile

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

const int maxn=;

const int inf=;

typedef long long ll;

int m,n;

int opt[maxn][maxn];

int a[maxn][maxn];

int tmp[maxn][maxn];

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

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

int getcolor(int x,int y)

{

    int ans=a[x][y];

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

    {

        int xx=x+dx[i];

        int yy=y+dy[i];

        if(xx>=&&xx<m&&yy>=&&yy<n)

            ans+=tmp[xx][yy];

    }

    return ans%;

}

int cal()

{

    int i,j;

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

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

            if(getcolor(i-,j))

                tmp[i][j]=;

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

        if(getcolor(m-,i))return -;

    int ans=;

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

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

        ans+=tmp[i][j];

    return ans;

}

void solve()

{

    int rec=-;

    int i,j;

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

    {

        memset(tmp,,sizeof(tmp));

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

        {

            tmp[][n-j-]=i>>j&;

        }

        int num=cal();

        if(num>=&&(rec>num||rec<))

        {

            rec=num;

            memcpy(opt,tmp,sizeof(tmp));

        }

    }

    if(rec<)

        printf("IMPOSSIBLE\n");

    else

    {

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

        {

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

            printf("%d%c",opt[i][j],j==n?'\n':' ');

            printf("\n");

        }

    }

}

int main()

{

    int  i,j,t,k;

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

    {

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

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

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

        solve();

    }

    return ;

}