1.一步之遥 （15’）
他的面前是两个按钮，分别写着“F”和“B”。
小明突然记起来，这两个按钮可以控制矿车在轨道上前进和后退。
按F，会前进97米。按B会后退127米。
透过昏暗的灯光，小明看到自己前方1米远正好有个监控探头。
他必须设法使得矿车正好停在摄像头的下方，才有机会争取同伴的援助。
或许，通过多次操作F和B可以办到。
矿车上的动力已经不太足，黄色的警示灯在默默闪烁...
每次进行 F 或 B 操作都会消耗一定的能量。
小明飞快地计算，至少要多少次操作，才能把矿车准确地停在前方1米远的地方。
请填写为了达成目标，最少需要操作的次数。
注意，需要提交的是一个整数，不要填写任何无关内容（比如：解释说明等）
题解思路： bfs，求最短路
answer = 97
#include<bits/stdc++.h>
using namespace std;
map<int,int>vis;
struct P
{
int x,step;
P(int x,int step):x(x),step(step){}
P(){}
};
int bfs()
{
queue<P>que;
P next;
que.push(P(0,0));
while(!que.empty()) {
P p = que.front();
que.pop();
if(p.x==1) return p.step;
next=P(p.x+97,p.step+1);
if(!vis[next.x]) {
vis[next.x] = 1;
que.push(next);
}
next=P(p.x-127,p.step+1);
if(!vis[next.x]) {
vis[next.x] = 1;
que.push(next);
}
}
}
int main()
{
int ans = bfs();
cout<<ans<<endl;
return 0;
}
2.凑平方数（35’）
把0~9这10个数字，分成多个组，每个组恰好是一个平方数，这是能够办到的。
比如：0, 36, 5948721
再比如：
1098524736
1, 25, 6390784
0, 4, 289, 15376
等等...
注意，0可以作为独立的数字，但不能作为多位数字的开始。
分组时，必须用完所有的数字，不能重复，不能遗漏。
如果不计较小组内数据的先后顺序，请问有多少种不同的分组方案？
注意：需要提交的是一个整数，不要填写多余内容。
解题思路（dfs+剪枝）
这道题思路很简单就是数据量大了，主要题意就是说让你把一个数字串分割，然后每个小分组都是平方数。
这道题可以从结果来推，先把10位以内所有平方数算出来当然要用到大整数不然会溢出。然后对这600多个数进行全排列，在排列过程中当然还要减支。
减支1：几个分组合在一起的字符串不能超过10个
减支2：剩下可用长度比当前选择的字符串长度还小后面就不用看了，因为我们生成平方数从小到大生成的，后面的数肯定比当前的大（这个减支不必须只是会大大降低时间）
减支3：当前选的数不能和前面已经选的字符串有相同字符
answer = 300#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1111;
const ll inf = 9876543210;
struct P
{
ll x;
int len;
int b[11];
P(ll x,int len):x(x),len(len){}
P(){}
}a[N];
set<int>s;
int ans ,n;
void print()
{
for(int i=1;i<30;i++) printf("%d\n",a[i].x);
}
bool work(ll num)
{
int len=0;
set<int>ss;
while(num) {
ss.insert(num%10);
num/=10;
len++;
}
if(len==ss.size()) return true;
return false;
}
void dfs(int id)
{
int i,j;
if(s.size()==10) {
ans++;
return;
}
for(i=id;i<=n;i++) {
if(a[i].len+s.size()>10) break;
for(j=1;j<=a[i].len;j++) {
if(s.find(a[i].b[j])!=s.end()) break;
}
if(j>a[i].len) {
for(j=1;j<=a[i].len;j++) s.insert(a[i].b[j]);
dfs(i+1);
for(j=1;j<=a[i].len;j++) s.erase(s.find(a[i].b[j]));
}
}
}
int main()
{
ll i,num;
int len,j;
a[1]=P(0,1);
a[1].b[1]=0;
n=1;
for(i=1;i*i<=inf;i++) {
len=0;
num=i*i;
while(num) {
len++;
num/=10;
}
num=i*i;
if(work(num)) {
a[++n]=P(num,len);
for(j=1;j<=len;j++) {
a[n].b[j]=num%10;
num/=10;
}
}
}
ans=0;
dfs(1);
cout<<ans<<endl;
}