文章

68

粉丝

691

获赞

26

访问

577.9k

头像
不如让我来写一个搜索
P1630 上海交通大学2019年机试题
发布于2020年5月31日 16:26
阅读数 11.8k

三个杯子的水量为状态,然后广度优先搜索,这样做的好处是:可以把一个简单题写的很长

 

#define ll long long
#define inf 0x3f3f3f3f
#define MAX 1000005
#define vec vector<int>
#define P pair<int,int>

struct sta {
	int a, b, c;
	sta(int x = 0, int y = 0, int z = 0) { a = x, b = y, c = z; }
	string conv() {
		return to_string(a) + to_string(b) + to_string(c);
	}
};

//将水量为a的杯子注入水量为b的杯子,b杯的容量限制为B
void zhushui(int & a, int & b, int B) {
	if (b == B)return;//没有空间或者a没有水
	int t = B - b;//b杯最多能装t
	if (t >= a)b += a, a = 0;
	else a -= t, b += t;
}

queue<sta> q; unordered_map<string, int>m;  unordered_map<int, int>sc;

//各个杯子的容量这种状态是否出现过
bool check(int a, int b, int c) {
	if (sc.find(c) == sc.end())
		sc[c] = 1;
	if (m.find(sta(a, b, c).conv()) == m.end()) {//没有出现过的状态
		m[sta(a, b, c).conv()] = 1;
		q.push(sta(a, b, c));
		return true;
	}
	else return false;
}

int main() {
	int A, B, C;
	while (cin >> A >> B >> C) {
		int re...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发