算法-路上跳坑步数

Question

一条路有k个坑，每次能跳平方数步长（1 4 9 16。。），不能跳到坑里，从a跳到b最少几步？

Answer 1

输入a b n(坑的数量) 坑的数组 数字后面都有空格，测试了下，由于是遍历所有的可能，执行速度很慢
循环多次输入时a b n的值有时候a b n的值会异常，MS读缓冲区有问题，出现这个问题时重启下程序就好了。---求高手分析原因
如有错误请指出~

#include "stdafx.h"
#include <iostream>
#include <map>
#include <stack>
using namespace std;

#define MAX 100
int step[MAX];

typedef stack<int> stack_int;
map<int,stack_int> map_result;
stack_int g_stack;

bool bFirst;
void init_step()
{
for(int i = 1; i <= MAX ; ++i)
step[i - 1] = i * i;
}
bool chek(int a,int* k,int n)
{
if(!n)
return false;
for(int i = 0; i <= n ; ++i)
if (a == k[i])
return true;

return false;
}
void fun(int a,int b,int* k,int n)
{
if (!map_result.empty() && g_stack.size() > map_result.begin()->first)
{
return;
}
if (!bFirst && g_stack.empty())
{
return;
}
if(a > b)
return;

if (a == b)
{
map_result[g_stack.size()] = g_stack;
return;
}
if (chek(a,k,n))
return;

bFirst = false;
for(int i = 0; i <= MAX ; ++i)
{
if(a + step[i] > b)
return;
g_stack.push(step[i]);
fun(a + step[i],b,k,n);
g_stack.pop();
}
}

void main()
{
init_step();
int a,b,n;
while(true)
{
bFirst = true;

printf("请输入a,b,n:");
scanf("%d %d %d",&a,&b,&n);

while(b <= a || n < 0)
{
printf("请输入a,b,n:");
scanf("%d %d %d",&a,&b,&n);
}

int* k = new int[n];
for(int i = 0; i < n; ++i)
scanf("%d",&k[i]);

fun(a,b,k,n);

if (map_result.empty())
{
printf("n无法到达n");
}
else
{
int i = (map_result.begin())->first;
g_stack = (map_result.begin())->second;
printf("n步数：%dn",i);
printf("%d",b);
int temp = b;
while( i-- )
{
temp -= g_stack.top();
printf("t ( - %d ) %d", g_stack.top(),temp );
g_stack.pop();
}
printf("nn");
}
map_result.clear();
delete[] k;
}
}

Answer 2

个人觉得回溯法比较现实点