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