HDOJ 5613 Baby Ming and Binary image - dblank

HDOJ 5613 Baby Ming and Binary image

问题描述
铭宝宝很喜欢像素图,所以,他喜欢把像素图都做如下的处理:
首先,把像素图变换成二值图(用0101表示),然后,在二值图中,把每个点以及和它相邻的点(最多99个点)的0101值加起来,并保存在一个矩阵Mat中。
铭宝宝选择的图像底边和顶边都是空白的(二值图中值为00),因为他觉得这样的图很漂亮。
不过因为矩阵很大,铭宝宝担心记录过程中出错。所以现在铭宝宝想知道,根据他所保存下来的矩阵Mat,是否能还原出二值
输入描述
输入TT表示测试组数(T \leq 30)(T≤30)
输入两个数n, mn,m表示二值图的大小(即矩阵M的大小) (2 < n \leq 12, m \leq 100)(2<n≤12,m≤100)
接下来输入nn行,每行mm个数,表示矩阵Mar
输出描述
输出Impossible,如果不能还原出二值图
输出Multiple,如果还原出来的二值图不唯一
否则输出二值图
输入样例
2
4 4
1 2 3 2
2 3 4 2
2 3 4 2
1 1 1 0
3 1
1
1
0
输出样例
0 0 0 0
0 1 1 1
0 1 0 0
0 0 0 0
Impossible
Hint
样例2中,因为[1 0 0]不是铭宝宝选择的矩阵,所以无解
先枚举出第一列的所有可能,然后第(i,j)个点的状态是第(i-1, j-1)的计数减去包括他的八个点的状态,状态都是唯一的,可以直接递推出来,然后过程中判断合不合法,并记录可能的方案数,最后输出就好了。

#include<cstdio>  
#include<algorithm>  
#include<map>  
#include<cstring>  
#include<map>  
#include<set>  
#include<queue>  
#include<stack>  
using namespace std;  
const int N = 1e2 + 10;  
const double eps = 1e-10;  
typedef long long ll;  
int Map[N][N], temp[N][N], n, m, ans[N][N];  
void getans()  
{  
    for(int i = 1; i<=m; i++)  
        for(int j = 1; j<=n; j++)  
            ans[i][j] = temp[i][j];  
}  
bool cheak(int num)  
{  
    memset(temp, 0, sizeof(temp));  
    for(int i = 0; i<m-2; i++)  
    {  
        temp[i+2][1] = (num>>i) & 1;  
        //cout<<temp[i+2][1]<<endl;  
    }  
    for(int j = 2; j<=n; j++)  
    {  
        for(int i = 2; i<=m+1; i++)  
        {  
            temp[i][j]=Map[i-1][j-1]-temp[i-2][j-2]-temp[i-1][j-2]-temp[i][j-2]-temp[i-2][j-1]-temp[i-1][j-1]-temp[i][j-1]-temp[i-2][j]-temp[i-1][j];  
            if(temp[i][j] != 0 && temp[i][j] != 1) return false;  
            if(i >= m && temp[i][j] != 0)return false;  
        }  
    }  
    for(int i = 1; i<=m; i++)  
        if(Map[i][n] != temp[i][n]+temp[i+1][n] + temp[i-1][n] + temp[i-1][n-1] + temp[i+1][n-1] +temp[i][n-1])  
            return false;  
    getans();  
    return true;  
}  
int main()  
{  
    int t;  
    cin>>t;  
    while(t--)  
    {  
        scanf("%d%d", &m, &n);  
        for(int i = 1; i<=m; i++)  
            for(int j = 1; j<=n; j++)  
                scanf("%d", &Map[i][j]);  
        int cnt = 0;  
        for(int i  = 0; i<(1<<(m-2)); i++)  
        {  
            if(cheak(i)) cnt++;  
            if(cnt>=2) break;  
        }  
        if(cnt>=2)  
            puts("Multiple");  
        else if(cnt == 0)  
            puts("Impossible");  
        else  
        {  
            for(int i = 1; i<=m; i++)  
                for(int j = 1; j<=n; j++)  
                {  
                    printf("%d", ans[i][j]);  
                    printf(j == n ?"\n" : " ");  
                }  
        }  
    }  
    return 0;  
}

 

相关文章

发表新评论