题解 | 时津风的资源收集

#include <iostream>
#include <queue>
#include <cstring> 

using namespace std;

int t;
int dest_10[305], dest_300[305];
queue<int> q;
int direction[6] = {1, -1, 10, -10, 100, -100};

//状态10变为target (10 <= target <= 300) 
void init() {
	int ans;
	q.push(10);
	dest_10[10] = 0;
	while (!q.empty()) {
		int e = q.front(); 
		q.pop();
		for (int i = 0; i < 6; i++) {
			int val = direction[i] + e; 
			if (val >= 10 && val <= 300 && dest_10[val] == -1) {
				dest_10[val] = dest_10[e] + 1;
				q.push(val);
			}
		}
	}
//	ans = dest[target];
	
//	memset(dest, 0xFF, sizeof(dest));
	q.push(300);
	dest_300[300] = 1;
	while (!q.empty()) {
		int e = q.front(); 
		q.pop();
		for (int i = 0; i < 6; i++) {
			int val = direction[i] + e; 
			if (val >= 10 && val <= 300 && dest_300[val] == -1) {
				dest_300[val] = dest_300[e] + 1;
				q.push(val);
			}
		}
	}
//	ans = min(ans, dest[target]);
	
//	return ans;
	for (int i = 10; i <= 300; i++) {
		dest_10[i] = min(dest_10[i], dest_300[i]);
	}
}

//1.状态就一个
//2.其实操作6是完全没用的，操作5最多执行一次，同时操作1 ~ 4其实不会同时出现 +a 和 -a
//操作5做特判（两次bfs）主要是不想在for(int i = 0; i < 6; i++)做特判，其实也可以一次bfs
//3.把a, b, c, d分开求因为是独立的，合起来求感觉复杂很多
int main () {
	cin >> t;
	int a, b, c , d;
	memset(dest_10, 0xFF, sizeof(dest_10));
	memset(dest_300, 0xFF, sizeof(dest_300));
	init();
	while (t-- > 0) {
		cin >> a >> b >> c >> d;
		cout << dest_10[a] + dest_10[b] + dest_10[c] + dest_10[d] << endl;
	}
}