一道简单的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>
[解决办法]
- 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; }