# 12306 - beat the monster
>author: Utin
###### tags: `BFS`

---

## Brief
See the code below

## Solution 0

#include <bits/stdc++.h>

struct State {
    int level, hp, mhp, step;
    State(int l, int h, int m, int s) : level(l), hp(h), mhp(m), step(s) {}
};

int L, HP, MHP, MDMG, table[15][2];
bool check[16][301][401]; // record whether the state has been used

std::queue<State> process;

int main() {
    std::cin >> L >> HP >> MHP >> MDMG;
    for (int i = 0; i < L; i++) 
        std::cin >> table[i][0] >> table[i][1];

    process.push(State(0, HP, MHP, 0));
    check[0][HP][MHP] = true;

    while (process.size()) {

        State curr = process.front();
        process.pop();

        // lose
        if (HP <= MDMG) break;

        // win
        if (curr.mhp <= table[curr.level][0]) {
            std::cout << curr.step + 1 << '\n';
            return 0;
        }

        // attack
        if (curr.hp > MDMG && !check[curr.level][curr.hp - MDMG][curr.mhp - table[curr.level][0]]) {
            process.push(State(curr.level, curr.hp - MDMG, curr.mhp - table[curr.level][0], curr.step + 1));
            check[curr.level][curr.hp - MDMG][curr.mhp - table[curr.level][0]] = true;
        }

        // heal
        if (curr.hp < HP) {
            int new_hp = curr.hp + table[curr.level][1];
            if (new_hp > HP) new_hp = HP;
            if (new_hp > MDMG && !check[curr.level][new_hp - MDMG][curr.mhp]) {
                process.push(State(curr.level, new_hp - MDMG, curr.mhp, curr.step + 1));
                check[curr.level][new_hp - MDMG][curr.mhp] = 1;
            }
        }

        // level up
        if (curr.level < L - 1 && curr.hp > MDMG) {
            process.push(State(curr.level + 1, curr.hp - MDMG, curr.mhp, curr.step + 1));
            check[curr.level + 1][curr.hp - MDMG][curr.mhp] = true;
        }

    }

    std::cout << -1 << '\n';

}

// By Utin

## Reference