题目链接: [Fliptile]
大致题意:
给出一个m*n的01矩阵，每次操作可以选一个位置，使它和它的上下左右翻转一次(0变1，1变0)，问最少多少次操作可以使所有数都变为0，如果有，输出翻转的方案，否则输出IMPOSSIBLE
解题思路:
二进制枚举，枚举第一行的所有情况，一共有2m种，只要第一行确定，矩阵其他的就都可以确定，最后判断最后一行是否全为0即可。
(判断每一行时，看上一行来确定当前行是否需要翻转，tmp记录上一行对当前行的影响)
AC代码:
#include<iostream>
typedef long long ll
;
using namespace std
;
const int INF
= 0x3f3f3f3f;
const int N
= 20;
int n
, m
;
int mp
[N
][N
];
int tmp
[N
][N
];
int ans
[N
][N
];
int fx
[][2] = { 0,1,1,0,-1,0,0,-1,0,0 };
int f(int x
, int y
) {
int cnt
= mp
[x
][y
];
for (int i
= 0; i
< 5; ++i
) {
int dx
= fx
[i
][0] + x
; int dy
= fx
[i
][1] + y
;
if (dx
>= 0 && dx
< n
&& dy
>= 0 && dy
< m
)
cnt
+= tmp
[dx
][dy
];
}
return cnt
% 2;
}
int solve() {
int cnt
= 0;
for (int i
= 1; i
< n
; ++i
) {
for (int j
= 0; j
< m
; ++j
) {
if (f(i
- 1, j
))tmp
[i
][j
] = 1;
}
}
for (int i
= 0; i
< m
; ++i
) {
if (f(n
- 1, i
))return INF
;
}
for (int i
= 0; i
< n
; ++i
) {
for (int j
= 0; j
< m
; ++j
) {
cnt
+= tmp
[i
][j
];
}
}
return cnt
;
}
int main(void)
{
int res
= INF
;
scanf("%d%d", &n
, &m
);
for (int i
= 0; i
< n
; ++i
) {
for (int j
= 0; j
< m
; ++j
) {
scanf("%d", &mp
[i
][j
]);
}
}
for (int i
= 0; i
< (1 << m
); ++i
) {
memset(tmp
, 0, sizeof tmp
);
for (int j
= 0; j
< m
; ++j
)
tmp
[0][j
] = i
>> j
& 1;
int sum
= solve();
if (sum
< res
) {
res
= sum
;
memcpy(ans
, tmp
, sizeof tmp
);
}
}
if (res
== INF
)printf("IMPOSSIBLE\n");
else {
for (int i
= 0; i
< n
; ++i
) {
for (int j
= 0; j
< m
; ++j
) {
printf("%d%c", ans
[i
][j
], j
== m
- 1 ? '\n' : ' ');
}
}
}
return 0;
}
END
