HDU 1195 深搜

本文主要是介绍HDU 1195 深搜，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

/*这个题目可以用深度优先搜索(DFS)做搜索的目的就是让每一位密码进行移动直到移动到可以使用最少的动作得到能打开箱子的密码为止
*/
#include<iostream>
#include<cmath>
using namespace std;
int a[4], b[4], v[4] = {0}, sum;int cup(int num)
{int t = 0,s[4] = {num/1000,num%1000/100,num%100/10,num%10};//将移动后的密码的每一位放在s数组中for(int i = 0; i < 4; i++)//记录要进行几次转动{if(abs(s[i]-b[i]) < 5) t += abs(s[i]-b[i]);else t += 9-abs(s[i]-b[i]);}return t;
}void dfs(int num, int k)//深搜函数
{if(num > 999){int t;t = cup(num) + k;if(sum > t)//比较，将最小的保存下来sum = t;return ;}for(int i = 0; i < 4; i++)if(!v[i]){v[i] = 1;dfs(num*10+a[i],k++);//k++表示已经移动了多少次，所以要用k++v[i] = 0;}
}int main()
{int t, n, m;cin >> t;while(t-- && cin >> n >> m){int j = 1;for(int i = 0; i < 4; i++)//将密码的每一位读出来放在数组中保存{a[i] = n/j%10;b[i] = m/j%10;j *= 10;}sum = 10000000;dfs(0,0);cout << sum << endl;}
}

这篇关于HDU 1195 深搜的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---