HDOJ 5613 Baby Ming and Binary image - dblank

# HDOJ 5613 Baby Ming and Binary image

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

#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;
}