[ARC001B] リモコン

题目传送门：[ARC001B] リモコン

求最小步，是dfs的例题。首先，偏移量不能少：

int d[6]={1,-1,5,-5,10,-10};

然后开始写搜索：

void dfs(int tem, int step) {  // 定义深度优先搜索函数dfs，参数tem表示当前温度，step表示已经走过的步数  
    if(tem > 40 || tem < 0 || flag[tem] == 1) return;  // 如果当前温度超出范围或者已经被访问过，直接返回  
    if(step > ans) return;  // 如果已经走过的步数大于当前的最小步数ans，直接返回  
    if(tem == b) {  // 如果当前状态等于目标状态b  
        ans = min(ans, step);  // 更新最小步数  
    }  
    flag[tem] = 1;  // 标记当前状态为已访问  
    for(int i = 0; i < 6; i++) {  // 遍历6种可能的增量  
        dfs(tem + d[i], step + 1);  // 递归调用dfs函数，进入下一个状态  
    }  
    flag[tem] = 0;
}  

起始温度就是a。

好的，我们来写完整代码：

#include<bits/stdc++.h>  // 包含大多数标准库  
using namespace std;     // 使用标准命名空间  
  
int a, b, ans = 1e9, flag[105];  // 定义全局变量a, b, ans, 和flag数组。ans初始化为10^9，flag数组用于标记某个状态是否已经被访问过  
  
int d[6] = {1, -1, 5, -5, 10, -10};  // 定义了一个数组d，用于存储6种可能的偏移量 
  
void dfs(int tem, int step) {  // 定义深度优先搜索函数dfs，参数tem表示当前温度，step表示已经走过的步数  
    if(tem > 40 || tem < 0 || flag[tem] == 1) return;  // 如果当前状态超出范围或者已经被访问过，直接返回  
    if(step > ans) return;  // 如果已经走过的步数大于当前的最小步数ans，直接返回  
    if(tem == b) {  // 如果当前温度等于目标状态b  
        ans = min(ans, step);  // 更新最小步数  
    }  
    flag[tem] = 1;  // 标记当前状态为已访问  
    for(int i = 0; i < 6; i++) {  // 遍历6种可能的增量  
        dfs(tem + d[i], step + 1);  // 递归调用dfs函数，进入下一个状态  
    }  
    flag[tem] = 0;  // 回溯，将当前状态标记为未访问  
}  
  
int main() {  // 主函数  
    cin >> a >> b;  // 输入起始状态a和目标状态b  
    dfs(a, 0);  // 从起始状态开始深度优先搜索  
    cout << ans;  // 输出最小步数  
    return 0;  // 程序结束  
}