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

擦。忘记输出次数一直wa!

Posted by cisjiong at 2012-07-28 00:44:52 on Problem 3414
1、单组数据
2、可能多种答案,随便输出一种就行
3、别忘了impossible,还有次数。
第一次在PKU贴代码
#include <cstdio>
#include <iostream>
#include <cstddef>
#include <string>
#include <cstring>
using namespace std;

const int maxn = 110;

struct Statue {
	int cnt, a[2];
	string op; // 0x: FILL(x); 1x: DROP(x); 2xy: POUR(x, y)
}que[maxn * maxn];

int A[2], C, front, tail;
int mark[maxn][maxn];

void drop(const Statue& nn, int id) {
	Statue node = nn;
	node.a[id] = 0;

	if (!mark[node.a[0]][node.a[1]]) {
		mark[node.a[0]][node.a[1]] = 1;

		node.op += "1";
		node.op += ('0' + (id + 1));
		++node.cnt;
		que[front++] = node;
	}
}

void fill(const Statue& nn, int id) {
	Statue node = nn;
	node.a[id] = A[id];

	if (!mark[node.a[0]][node.a[1]]) {
		mark[node.a[0]][node.a[1]] = 1;

		node.op += "0";
		node.op += ('0' + (id + 1));
		++node.cnt;
		que[front++] = node;
	}
}

void pour(const Statue& nn, int f, int t) {
	Statue node = nn;
	int sum = (node.a[f] + node.a[t]);

	if (sum > A[t]) {
		node.a[t] = A[t];
		node.a[f] = sum - A[t];
	} else {
		node.a[f] = 0;
		node.a[t] = sum;
	}

	if (!mark[node.a[0]][node.a[1]]) {
		mark[node.a[0]][node.a[1]] = 1;
		++node.cnt;
		node.op += "2";
		node.op += ('0' + (f + 1));
		node.op += ('0' + (t + 1));
		que[front++] = node;
	}
}

bool bfs() {
	while (tail < front) {
		Statue node = que[tail++];

		if (node.a[0] == C || node.a[1] == C) {
			printf("%d\n", node.cnt);
			size_t sz = node.op.size();
			for (size_t i = 0; i != sz; ++i) {
				if (node.op[i] == '0') {
					cout << "FILL(" << node.op[++i] << ")" << endl;
				} else if (node.op[i] == '1') {
					cout << "DROP(" << node.op[++i] << ")" << endl;
				} else {
					cout << "POUR(" << node.op[++i] << ",";
					cout << node.op[++i] << ")" << endl;
				}
			}
			return true;
		}

		if (node.a[0]) {
			drop(node, 0);
			if (node.a[1] < A[1]) pour(node, 0, 1);
		}

		if (node.a[0] < A[0]) fill(node, 0);

		if (node.a[1]) {
			drop(node, 1);
			if (node.a[0] < A[0]) pour(node, 1, 0);
		}

		if (node.a[1] < A[1]) fill(node, 1);
	}
	return 0;
}

int main() {
	scanf ("%d%d%d", &A[0], &A[1], &C);
	if (C == 0) {
		puts("0");
		return 0;
	}

	if (A[0] == C) {
		puts("1\nFILL(1)"); 
	} else if (A[1] == C) {
		puts("1\nFILL(2)"); 
	} else {
		Statue node;
		front = tail = 0;
		node.a[0] = 0, node.a[1] = 0;
		node.cnt = 0, node.op = "";
		que[front++] = node;

		memset(mark, 0, sizeof (mark)); 
		mark[0][0] = 1;
		if (!bfs()) puts("impossible");
	}

	return 0;
}

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