一道简单的ACM题目解决办法
一道简单的ACM题目
TOM 设计了一个可以前进或后退的机器人，该机器人在每个位置i会得到一个移动步数的指令Ki(i=1,2……N)
聪明的机器人判断是应该前进Ki步还是倒退Ki步
例如给定指令序列（3 3 1 2 5），表示机器人在第一个位置时可以前进3个位置到第4个位置，此时不可以倒退，因为倒退就越界了（1-3=-2）在第2个位置可以前进3个位置，此时还不可以倒退，在第3个位置上可以前进1个位置到第4个位置，或者后退1个位置到第2个位置……
问：对于给定的序列指(x1,x2,x3……)和A B两个位置，机器人从A到B，至少要判断几次？
要求：
输入:
第一行：M 表示下面要测试的数据组数。
接下来每组两行数据
头一行N A B（n表示指令数，1<N<50,1<=A,B<=N）
下一行:k1,k2,k3……kn(0<ki<=N)
输出：机器人从A到B至少要判断的次数,若走不到B输出-1；
样例：5 1 2
3 3 1 2 5
8 5 3
1 2 1 5 3 1 1 1
输出 3
-1
------解决方案--------------------
------解决方案--------------------
先对每个结点建立一个入度表(最好用hash表做)。取B点作为初始当前集合，同时删除掉B的出度(最多两个)。
<loop>取出当前集合的所有入度表做为当前集合，同时删除当前集合的所有出度。当前集合长度为0或A在其中则结束，否则循环。</loop>
------解决方案--------------------
TOM 设计了一个可以前进或后退的机器人，该机器人在每个位置i会得到一个移动步数的指令Ki(i=1,2……N)
聪明的机器人判断是应该前进Ki步还是倒退Ki步
例如给定指令序列（3 3 1 2 5），表示机器人在第一个位置时可以前进3个位置到第4个位置，此时不可以倒退，因为倒退就越界了（1-3=-2）在第2个位置可以前进3个位置，此时还不可以倒退，在第3个位置上可以前进1个位置到第4个位置，或者后退1个位置到第2个位置……
问：对于给定的序列指(x1,x2,x3……)和A B两个位置，机器人从A到B，至少要判断几次？
要求：
输入:
第一行：M 表示下面要测试的数据组数。
接下来每组两行数据
头一行N A B（n表示指令数，1<N<50,1<=A,B<=N）
下一行:k1,k2,k3……kn(0<ki<=N)
输出：机器人从A到B至少要判断的次数,若走不到B输出-1；
样例：5 1 2
3 3 1 2 5
8 5 3
1 2 1 5 3 1 1 1
输出 3
-1
------解决方案--------------------
------解决方案--------------------
先对每个结点建立一个入度表(最好用hash表做)。取B点作为初始当前集合，同时删除掉B的出度(最多两个)。
<loop>取出当前集合的所有入度表做为当前集合，同时删除当前集合的所有出度。当前集合长度为0或A在其中则结束，否则循环。</loop>
------解决方案--------------------
- C# code
public static int minJump(int[] jump, int start, int end)
{
//如果确定长度小于50，用位图替代HashSet，应该能提升几倍的效率
int value = -1;
if (jump != null)
{
int length = jump.Length;
if (length != 0 && --start >= 0 && --end >= 0 && start < length && end < length)
{
value = 0;
if (start != end)
{
#region 建立入度表
int left, right;
HashSet<int>[] jumpIn = new HashSet<int>[length];
for (int index = length - 1; index >= 0; index--)
{
if (index != end)
{
if ((right = (index << 1) - (left = index - jump[index])) < length)
{
if (jumpIn[right] == null) jumpIn[right] = new HashSet<int>();
jumpIn[right].Add(index);
}
if (left >= 0)
{
if (jumpIn[left] == null) jumpIn[left] = new HashSet<int>();
jumpIn[left].Add(index);
}
}
}
#endregion
if (jumpIn[end] == null) value--;
else
{
value++;
if (!jumpIn[end].Contains(start))
{
#region 初始化 当前集合
HashSet<int> currentIndex = new HashSet<int>();
foreach (int nextIndex in jumpIn[end])
{
if (jumpIn[nextIndex] != null)
{
currentIndex.Add(nextIndex);
if ((right = (nextIndex << 1) - (left = nextIndex - jump[nextIndex])) < length && right != end)
{
if (jumpIn[right].Count == 1) jumpIn[right] = null;
else jumpIn[right].Remove(nextIndex);
}
if (left >= 0 && left != end)
{
if (jumpIn[left].Count == 1) jumpIn[left] = null;
else jumpIn[left].Remove(nextIndex);
}
}
}
#endregion
if (currentIndex.Count == 0) value = -1;
else
{
for (HashSet<int> nextIndexs; value != -1; currentIndex = nextIndexs)
{
#region 取出当前集合的所有入度表做为当前集合
nextIndexs = new HashSet<int>();
foreach (int index in currentIndex)
{
if (jumpIn[index] != null)
{
if (jumpIn[index].Contains(start))
{
nextIndexs.Add(start);
break;
}
else
{
foreach (int nextIndex in jumpIn[index])
{
if (jumpIn[nextIndex] != null)
{
nextIndexs.Add(nextIndex);
if ((right = (nextIndex << 1) - (left = nextIndex - jump[nextIndex])) < length && right != index)
{
if (jumpIn[right].Count == 1) jumpIn[right] = null;
else jumpIn[right].Remove(nextIndex);
}
if (left >= 0 && left != index)
{
if (jumpIn[left].Count == 1) jumpIn[left] = null;
else jumpIn[left].Remove(nextIndex);
}
}
}
}
}
}
#endregion
if (nextIndexs.Count == 0) value = -1;
else
{
value++;
if (nextIndexs.Contains(start)) break;
}
}
}
}
}
}
}
}
return value;
}