| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
呃,我是多蠢,没有IMPOSSIBLE就提交了#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iomanip>
#include<iostream>
#include<algorithm>
using namespace std;
/* POJ 3279 */
const int N = 20;
const int INF = 1e9 + 7;
bool G[N][N];
bool T[N][N];
int n, m, ans = INF, pre;
const int mv[5][2] = {
0,0,1,0,0,1,-1,0,0,-1
};
inline void putMatrix(void) {
puts(""); puts("/////Matrix/////");
for (int i = 1; i <= n; i++, puts(""))
for (int j = 1; j <= m; j++)
printf("%d ", T[i][j]);
}
inline void change(int x, int y) {
for (int i = 0; i < 5; i++)
T[x + mv[i][0]][y + mv[i][1]] ^= 1;
}
inline bool check(void) {
for (int i = 1; i <= m; i++)
if (T[n][i])return false;
return true;
}
inline int solve(int p) {
memcpy(T, G, sizeof(T));
int res = 0;
for (int i = 0; i < m; i++)
if ((p >> i) & 1)res++, change(1, i + 1);
for (int i = 1; i < n; i++)
for (int j = 1; j <= m; j++)
if (T[i][j])res++, change(i + 1, j);
//putMatrix();
return check() ? res : INF;
}
inline void printAnswer(int p) {
memcpy(T, G, sizeof(T));
for (int i = 0; i < m; i++) {
printf("%d ", (p >> i) & 1);
if ((p >> i) & 1)change(1, i + 1);
}puts("");
for (int i = 1; i < n; i++, puts(""))
for (int j = 1; j <= m; j++) {
printf("%d ", T[i][j]);
if (T[i][j])change(i + 1, j);
}
}
signed main(void) {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
scanf("%d", &G[i][j]);
for (int i = 0, tmp; i < (1 << m); i++)
if (ans > (tmp = solve(i)))ans = tmp, pre = i;
if (ans < INF)printAnswer(pre);
else puts("IMPOSSIBLE");
#ifndef ONLINE_JUDGE
system("pause");
#endif // !ONLINE_JUDGE
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator