【BFS】BISHI84 时津风的资源收集

思路

求解代码

// 定义一个静态数组dist，用于存储从数字10到其他数字的最小步数privatestaticint[]dist=newint[301];publicstaticvoidmain(String[]args)throwsIOException{// 调用bfs方法计算最小步数bfs();// 初始化输入输出流BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in));PrintWriterout=newPrintWriter(newOutputStreamWriter(System.out));// 读取测试用例数量intT=Integer.parseInt(br.readLine().trim());// 处理每个测试用例while(T-->0){// 读取一行输入并分割成字符串数组String[]str=br.readLine().trim().split("\\s+");// 将字符串数组转换为四个整数inta=Integer.parseInt(str[0]);intb=Integer.parseInt(str[1]);intc=Integer.parseInt(str[2]);intd=Integer.parseInt(str[3]);// 计算四个数字的最小步数之和intans=dist[a]+dist[b]+dist[c]+dist[d];// 输出结果out.println(ans);}// 刷新并关闭输出流out.flush();out.close();// 关闭输入流br.close();}/** * 使用BFS算法计算从数字10到其他数字的最小步数 * 可以进行的操作包括：+1, -1, +10, -10, +100, -100 * 特殊情况：可以直接跳到数字10或300 */privatestaticvoidbfs(){// 初始化dist数组，-1表示未访问Arrays.fill(dist,-1);// 创建队列用于BFS遍历Queue<Integer>queue=newLinkedList<>();// 设置起点数字10的步数为0dist[10]=0;// 将起点加入队列queue.add(10);// 定义可能的操作数组int[]ops={1,-1,10,-10,100,-100};// 当队列不为空时继续遍历while(!queue.isEmpty()){// 取出队首元素intu=queue.poll();// 创建邻居列表List<Integer>neighbors=newArrayList<>();// 应用所有可能的操作生成邻居for(intop:ops){neighbors.add(u+op);}// 添加特殊邻居：10和300neighbors.add(10);neighbors.add(300);// 遍历所有邻居for(intv:neighbors){// 如果邻居在有效范围内且未被访问过if(v>=10&&v<=300&&dist[v]==-1){// 更新步数dist[v]=dist[u]+1;// 将邻居加入队列queue.add(v);}}}}