题目分析
1. 存储方式
这道题目唯一的难点就是怎么存储地图,于是,我就想到了用一维数组来代替二维数组,因为题目说 ,所以我们只需要定义一个大小为 的数组来存储就行了。
2. 判断边界
由于我们用了一维数组存储,所以我们只需要判断 与 是否超出地图边界即可,至于怎么判断,我们可以找到下一步要走到的地方是否为 或是否超过了 。
3. 遍历数组
题目要求我们求出最小的没有走过的数,因此我们必须得尽量地走数字小的路径。
我们只需要贪心一波,判断我们右面的最小值与下面的最小值,然后朝最小值更小的方向走。
我们可以画图:
这张图中,我们肯定是向下走,因为向右走就没有办法走到 了。
4. 核心代码
1. 递归写法
bool check(int now2) {
int res = 2147483646;
for (int j = now2 + m; j <= k; j += m) res = (res < a[j] ? res : a[j]);
int res2 = 2147483646;
for (int i = now2 + 1; (i - 1) % m != 0 && i <= k; i++) res2 = (res2 < a[i] ? res2 : a[i]);
return res < res2;
}
void dfs(int now2) {
b[a[now2]] = 1;
if (now2 == k) {
for (int i = 0; i <= k + 10; i++) {
if (!b[i]) {
printf("%d", i);
return;
}
}
}
if (now2 + m <= k) {
if (now2 % m != 0 && now2 + 1 <= k) {
if (check(now2))
dfs(now2 + m);
else
dfs(now2 + 1);
} else
dfs(now2 + m);
} else
dfs(now2 + 1);
}
2. 递推写法
bool check(int now2) {
int res = 2147483646;
for (int j = now2 + m; j <= k; j += m) res = (res < a[j] ? res : a[j]);
int res2 = 2147483646;
for (int i = now2 + 1; (i - 1) % m != 0 && i <= k; i++) res2 = (res2 < a[i] ? res2 : a[i]);
return res < res2;
}
void fs(int now2) {
while (now2 != k) {
b[a[now2]] = 1;
if (now2 + m <= k) {
if (now2 % m != 0 && now2 + 1 <= k) {
if (check(now2))
now2 += m;
else
now2++;
} else
now2 += m;
} else
now2++;
b[a[now2]] = 1;
}
for (int i = 0; i <= k + 10; i++) {
if (!b[i]) {
printf("%d", i);
return;
}
}
}