有个奇怪的问题 虽然AC了,但还是不太明白
使用动态规划,代码如下:
#include<stdio.h>
#include<stdlib.h>
#define min(a,b) (a<b)?a:b
#define INF 1e9
int val[205];
int step[201][201];//step[i][j]从i 到j的最小次数
int main()
{
int n, sou, des;
scanf("%d%d%d", &n, &sou, &des);
int i, j, k;
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
if (i != j)
step[i][j] = INF;
else
step[i][j] = 0;
for (i = 1; i <= n; i++)
{
scanf("%d", &val[i]);
if (val[i] == 0)
continue;
int j = i + val[i];
int k = i - val[i];
if (j <= n)
step[i][j] = 1;
if (k >= 1)
step[i][k] = 1;
}
int t;
for (t = 1; t <= 50; t++)
{
for (i = 1; i <= n; i++)
{
for (j = n; j >= 1; j--)
{
for (k = 1; k <= n; k++)
{
step[i][j] = min(step[i][j], step[i][k] + step[k][j]);
}
}
}
}
if (step[sou][des] != INF)
printf("%d", step[sou][des]);
else
printf("-1");
return 0;
}
注意
在循环这里有四层,但是最外层只有25次,如果没有这层循环的话,代码会WA两个点#9 #10,但是这层循环的意义不是很懂
向大佬求教