1947.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/* This Code is Submitted by wywcgs for Problem 1947 on 2006-12-26 at 15:28:00 */
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

const int LMT = 10000000;
const int TEN[] = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000 };

class BitVector {
private:
	int bit[LMT>>5];
public:
	void clear() { memset(bit, false, sizeof(bit)); }
	bool test(int k) const { return ((bit[k>>5])>>(k&31))&1; }
	void set(int k) { bit[k>>5] |= 1 << (k&31); }
};

BitVector bv;
queue<int> Q;

int bfs(int, int);
bool generate(int, int, int, int);

int main()
{
	int b, e;

	for(int t = 1; scanf("%d %d", &b, &e) == 2; t++)
		printf("%d. %d\n", t, bfs(b, e));
	
	return 0;
}

int bfs(int b, int e)
{
	if(b == e) return 0;
	while(!Q.empty()) Q.pop();
	bv.clear(); bv.set(b);
	Q.push(b); Q.push(0);
	while(!Q.empty()) {
		int a = Q.front(); Q.pop();
		int step = Q.front()+1; Q.pop();
		if(generate(a, 0, step, e)) return step;
	}
	return -1;
}
bool generate(int a, int sum, int step, int e)
{
	if(a == 0) {
		if(bv.test(sum)) return false;
		bv.set(sum);
		if(step < 8) { Q.push(sum); Q.push(step); }
		return (e == sum);
	}
	for(int i = 1, d = 0; i < 5; i++) {
		d += TEN[i-1]*(a%10);
		a /= 10;
		if(d*d+sum >= LMT) break;
		else if(generate(a, d*d+sum, step, e)) return true;
		if(a == 0) break;
	}
	return false;
}