#1107リモート制御問題c++


今は100番チャンネルにいます.移動するチャンネルNは5457であり、6,7,8ボタンが故障した場合、5455,++に移動する.全部で6回ボタンを押せばいいです.
つまり、大きさにかかわらず、一番近い数字+、-.
最初は数学的に接近して、仕事の位置から、元のNの位置と誤差範囲が一番小さい数字を探す変な考え(?)しました.
問題を解くのに力を入れて解決するのは簡単ですが、考えなければならないことやコードは少し混乱しています.
1.障害ボタンの数値を入力し、障害数値に1の値を入力します.(bool broken[i]=true)
2.まずNから小さくなる場合と大きくなる場合に分けます.(演算速度を最小限に抑えるため)
2-1. Nから小さくなります.

check()関数iが数字ボタンで押すことができる数字であるかどうかをチェックします.
押すことができれば、数字iの長さと(長さをstring型に変換するのが簡単)+数字iと移動するチャネルとの差(abs(i-n)の和を求める.
従来retは、移動するチャンネルと現在のチャンネル100との差を記憶していた.つまり、すべて+または-に移動します.
小さい値の1つをretに再保存します.
i値が存在する場合は、直ちに中断して重複文を終了します.最近の数字を求めればいいので、もうしなくてもいいです.
2-2. Nから増大する.

コードは2-1の場合と同じです.ここでiの値は常にn以上であるためabs演算を用いる必要はない.
MAXは100000に設定されていますが、移動するチャンネルの最大値は500000ですが、5、6、7、8、9の数字が故障する場合もあるので2倍に設定します.この部分が一番理解しにくい.
3.check()はwhileドアを迂回し、動作位置から故障数があるかどうかを順番にチェックします.
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;
int n, m;
const int MAX = 1000000;
vector<bool>broken(10);

void input() {
	cin >> n >> m;

	int k;
	for (int i = 0; i < m; i++) {
		cin >> k;
		broken[k] = true;
	}
}


bool check(int k) {

	if (k == 0)
		return broken[0] ? false : true;

	while (k) {
		if (broken[k % 10] == 1)
			return false;
		k /= 10;
	}
	return true;
}

int solution() {

	int ret = abs(n - 100);
	int tmp;

	if (m == 10)
		return ret;

	for (int i = n; i>=0; i--) {
		if (check(i)) {
			tmp = to_string(i).length() + abs(i - n);
			ret = min(ret, tmp);
			break;
		}
	}

	for (int i = n; i <= MAX; i++) {
		if (check(i)) {
			tmp = to_string(i).length() + abs(i - n);
			ret = min(ret, tmp);
			break;
		}
	}

	return ret;
}
int  main() {
	input();
	cout << solution() << endl;

	return 0;
}