# 12991 - Toad Jumping
>author: Utin
###### tags: `recursion`

---

## Brief
See the code below

## Solution 0

#include <stdio.h>

int length, s, t;//length: 石頭數量, s: 起點, t: 終點
int stone[1001][3];//[0]: 高度, [1]: 顏色, [2]: 是否踩過
int pass_case[2];//[0]: 耗能, [1]: 步數

int abs(int a);
int energy(int height_i, int height_j, int index_i, int index_j);
void jump(int index, int sum_e, int sum_s);

int main() {
    scanf("%d %d %d", &length, &s, &t);
    for(int i = 0; i < length; i++) {
        scanf("%d", &stone[i][0]);
    }
    for(int i = 0; i < length; i++) {
        scanf("%d", &stone[i][1]);
    }

    //題目很搞事不把0當第一項
    s -= 1;
    t -= 1;

    jump(s, 0, 0);
    printf("%d %d\n", pass_case[0], pass_case[1]);
}

//絕對值
int abs(int a) {
    if(a >= 0) return a;
    else return -a;
}

//計算消耗的能量
int energy(int height_i, int height_j, int index_i, int index_j) {
    return (abs(height_i-height_j) * abs(index_i-index_j));
}

void jump(int index, int sum_e, int sum_s) {
    //設成已經踩過
    stone[index][2] = 1;

    //到終點
    if(index == t) {
        //取耗能最多的
        if(sum_e > pass_case[0]) {
            pass_case[0] = sum_e;
            pass_case[1] = sum_s;
        }
        //耗能相同取步數多的
        else if(sum_e == pass_case[0] && sum_s > pass_case[1]) {
            pass_case[1] = sum_s;
        }
    }

    //還沒到終點
    else {
        //每一點都試試
        for(int i = 0; i < length; i++) {
            //不用試自己本身或已踩過的石頭
            if(i != index && stone[i][2] != 1) {
                //顏色相同或只隔一顆石頭才能跳
                if(stone[index][1] == stone[i][1] || i == index-1 || i == index+1) {
                    //確定下顆石頭能跳要計算能量消耗
                    int temp = sum_e + energy(stone[index][0], stone[i][0], index, i);
                    //跳去下一顆石頭
                    jump(i, temp, sum_s+1);
                }
            }
        }
    }

    //這行必加，我卡超久，遞迴退出來要還原成沒踩過的狀態
    stone[index][2] = 0;
}

// By Utin

## Reference