题解 | 时津风的资源收集

/*先计算出从10出发到所有可能位置的最短操作次数，之后根据输入的数据直接查找就行*/
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

vector<int> res(301, -1);//全局变量存储到可能位置的最短次数，初始化为-1

//bfs函数，为res数组赋值
void bfs(){
    queue<int> q;
    q.push(10);
    res[10] = 0;
    while(!q.empty()){
        int current = q.front();
        q.pop();
        //遍历邻接点
        int next[8] = {current + 1, current - 1, current + 10, current - 10, current + 100, current - 100, 10, 300};
        for(int i : next){
            if(i >= 10 && i <= 300 && res[i] == -1){
                q.push(i);
                res[i] = res[current] + 1;
            }
        }
    }
}

int main() {
    // 标准竞赛输入输出优化
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //调用bfs函数
    bfs();
    //输入数据
    int t;
    cin >> t;
    int a, b, c, d;

    int result;//计算结果并输出
    for(int i = 0; i < t; i++){
        cin >> a >> b >> c >> d;
        result = res[a] + res[b] + res[c] + res[d];
        cout << result << '\n';
    }
    
    return 0;
}
// 64 位输出请用 printf("%lld")