Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

呃,我是多蠢,没有IMPOSSIBLE就提交了

Posted by youshiki at 2016-08-26 16:30:14 on Problem 3279
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator