C++

DFS

#include <cstdio>

#include <cstdlib>

#include <algorithm>

#include <cstring>

using namespace std;

 

int Now,Final;

 

 

int min_=1000000;

void DFS(int n,int t){

    if(n==Final)

    {

        if(min_ > t)

            min_ = t;

        return;

    }

    if(t>=min_)

        return;

 

    if(n>Final){

        DFS(n-1,t+1);

        DFS(n-5,t+1);

        DFS(n-10,t+1);

    }else{

        DFS(n+1,t+1);

        DFS(n+5,t+1);

        DFS(n+10,t+1);

    }

}

 

 

int main()

{

    scanf("%d %d",&Now,&Final);

    DFS(Now,0);

    printf("%d",min_);

    return 0;

}

BFS

#include <cstdio>

#include <cstdlib>

#include <algorithm>

#include <queue>

#include <cstring>

using namespace std;

int Now,Final;

 

queue<int> q;

int t=0;

void BFS(){

    q.push(Now);

    while(!q.empty()){

        size_t size_=q.size();

        for(size_t i=0;i<size_;i++){

 

            int n=q.front();

            q.pop();

 

            if(n==Final){

                return;

            }

            q.push(n-1);

            q.push(n-5);

            q.push(n-10);

            q.push(n+1);

            q.push(n+5);

            q.push(n+10);

 

        }

        if(!q.empty())

            t++;

    }

}

 

int main()

{

    scanf("%d %d",&Now,&Final);

    BFS();

    printf("%d",t);

    return 0;

}

DP

#include <cstdio>

#include <cstdlib>

#include <algorithm>

#include <queue>

#include <cstring>

using namespace std;

int dt[70];

int Now,Final;

 

 

const int INF = 100;

const int offset = 10;

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

int dp()

{

    if(Now > Final)

        swap(Now, Final);

    int s = Now - offset;

    if(s < 0)

    {

        Now += -s;

        Final += -s;

        s = 0;

    }

    int e = Final + offset;

 

    for(int i = s; i <= e; ++i)

        dt[i] = INF;

 

    dt[Now] = 0;

    for(int k = 0; k < 6; ++k)

        dt[Now + dx[k]] = 1;

    for(int i = s; i <= e; i++){

        for(int k = 0; k < 6; ++k)

        {

            if(i + dx[k] >= s && i + dx[k] <= e)

                dt[i + dx[k]] = min(dt[i + dx[k]], dt[i] + 1);

        }

    }

    return dt[Final];

}

 

int main()

{

    scanf("%d %d",&Now,&Final);

    printf("%d",dp());

    return 0;

}