完成给定场景的最短路径

换一种方式思考。有效的解决方案只能由有效的数字组成

---

1. 通过从所有可能的按钮中删除出现故障的按钮来构建有效的按钮集

   0,1,3,4,6,7

2. 从左到右查找通道号的第一个无效数字如果找到，请转到步骤3。否则，不需要遍历按钮

3. 仅在设置有效按钮的情况下，生成两侧最接近通道编号的两个数字。

   例如：通道编号=189

   盲第一个无效数字右侧的所有数字->18x

   上限：从有效集合中查找稍大的数字8，但未找到。在这种情况下，我们寻找一个更大的有效数字1，我们得到3。然后用最小的有效数字填充其余部分。我们得到300。

   下界：从有效集合中寻找一个稍小的数字8，我们得到7。然后把最大的有效数字加起来，得到177。

4. 如果不能形成下限或上限（通道编号450应为0作为有效解）并且超出上限，则考虑边界情况

5. 将这两个数字与通道编号进行比较，得到最接近的数字。

6. 格式化和输出

---

时间复杂度：所有情况下的O（log（n））

对于电视遥控器，我们可以做出一些假设：

• 它不加起来，所以我们必须从最近的频道开始使用+1或-1按钮
• 当达到上限时，+1将变为最低数，-1以相同的方式向另一个方向作用

从这些假设开始，找到在任一方向上步骤最少的通道：

public int NearestChannel(int channel)
{
   var forward = StepsForward(channel);
   var backward = StepsBackward(channel);
   if (forward < backward)
   {
      return channel - forward;
   }
   else
   {
      return channel + backward;
   }
}

StepsForward和StepsBackward方法只是简单地计数，直到我们得到有效的结果。唯一需要注意的是上限和下限（在您的示例中为0和450）：

public int StepsForward(int channel)
{
   int steps = 0;
   while (!IsValid(channel))
   {
      channel--;
      if (channel < 0)
      {
         channel = 450;
      }
      steps++;
   }
   return steps;
}
public int StepsBackward(int channel)
{
   int steps = 0;
   while (!IsValid(channel))
   {
      channel++;
      if (channel > 450)
      {
         channel = 0;
      }
      steps++;
   }
   return steps;
}

然后，验证只是查看要测试的数字是否包含任何无效数字：

public bool IsValid(int number)
{
   var numberAsString = number.ToString();
   foreach (var digit in numberAsString)
   {
      switch (digit)
      {
         case '2':
         case '5':
         case '8':
         case '9':
            return false;
      }
   }
   return true;
}

*更新并检查错误，最终解决方案可能是这样的：

    public static void Traverse(int channelToAccess, int maxChannels, params char[] brokenButtons)
    {      
        int result = -1;      // closest channel num
        for (int i = 1; result == -1 && i > 0 && i < maxChannels; i++)
        {
            if (!(channelToAccess + i).ToString().Any(brokenButtons.Contains)) { result = channelToAccess + i; break; }
            if (!(channelToAccess - i).ToString().Any(brokenButtons.Contains)) { result = channelToAccess - i; break; }
        }
       int difference = result - channelToAccess;
       Console.WriteLine("To open channel {0} you should turn channel {1} and press {2} button {3} times", channelToAccess, result, difference > 0 ? "-" : "+", Math.Abs(difference));
    }

用法示例：Traverse(255, 450, '2', '5', '8', '9');

输出：要打开通道255，您应该打开通道300并按下按钮"-"45次

我相信这是按预期进行的
它可以进一步优化，但这是我现在能做的最好的。

格式化是必要的，因为当用户键入8、9或89..99时，会出现拐角情况，在这些情况下，小数位数会发生变化，这是我找到的唯一解决方法。

class RemoteControl
{        
    public char[] brokenButtons = new char[4] {'2','5','8','9'};
    public char[] availableButtons = new char[6] { '0', '1', '3', '4', '6', '7'};        
    public char[] allButtons = new char[10] {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
    private char[] HighestPriorChannel(char[] inputChannel)
    {
        char[] channel = inputChannel.ToArray();            
        int pos;
        bool changed, isMarked = false;
        for (int i = channel.Length - 1; i >= 0; i--)
        {
            changed = false;
            pos = Array.IndexOf<char>(allButtons, channel[i]);
            if (isMarked) pos--;
            while (pos >= 0)
            {
                channel[i] = allButtons[pos];
                pos--;
                if (!brokenButtons.Contains(channel[i])) break;
                else changed = true;
            }
            if (isMarked || changed)
            {
                for (int j = i + 1; j < channel.Length; j++)
                    channel[j] = availableButtons.Last();
            }
            isMarked = brokenButtons.Contains(channel[i]);
        }            
        return channel;
    }
    private char[] LowestNextChannel(char[] inputChannel)
    {
        char[] channel = inputChannel.ToArray();         
        int pos;
        bool changed, isMarked = false;
        for (int i = channel.Length - 1; i >= 0; i--)
        {
            changed = false;
            pos = Array.IndexOf<char>(allButtons, channel[i]);
            if (isMarked) pos++;
            while(pos < allButtons.Length)
            {
                channel[i] = allButtons[pos];
                pos++;
                if (!brokenButtons.Contains(channel[i])) break;
                else changed = true;
            }
            if (isMarked || changed)
            {
                for (int j = i + 1; j < channel.Length; j++)
                    channel[j] = availableButtons.First();
            }
            isMarked = brokenButtons.Contains(channel[i]);
        }            
        return channel;
    }
    private int FindNearestChannel(char[] channel)
    {
        char[] prior = HighestPriorChannel(channel);
        char[] next = LowestNextChannel(channel);
        int intChannel = Convert.ToInt32(new string(channel));
        int intPrior = Convert.ToInt32(new string(prior));
        int intNext = Convert.ToInt32(new string(next));
        bool nextInRange = IsChannelInRange(intNext);
        bool priorInRange = IsChannelInRange(intPrior);
        if (nextInRange && priorInRange)
        {
            if ((intChannel - intPrior) > (intNext - intChannel))
            {
                return intNext;
            }
            else
            {
                return intPrior;
            }
        }
        else if (nextInRange)
        {
            return intNext;
        }
        else
        {
            return intPrior;
        }
    }
    private void GoBackward(int desiredChannel, int nearestChannel)
    {
        int times = 0;
        while (desiredChannel != nearestChannel)
        {
            nearestChannel--;
            times++;
        }
        Console.WriteLine("Press button (-) {0} times", times);
    }
    private void GoForward(int desiredChannel, int nearestChannel)
    {
        int times = 0;
        while(desiredChannel != nearestChannel){
            nearestChannel++;
            times++;
        }
        Console.WriteLine("Press button (+) {0} times", times);
    }
    public void FindChannel(string channel)
    {
        if (channel.Intersect(brokenButtons).Count() > 0)
        {                
            int nearestChannel = FindNearestChannel(channel.ToArray());
            Console.WriteLine("Turn Channel {0}", nearestChannel);
            int asInt = Convert.ToInt32(channel);
            if (asInt > nearestChannel)
                GoForward(asInt, nearestChannel);
            else
                GoBackward(asInt, nearestChannel);
        }
        else
        {
            Console.WriteLine("Turn Channel {0}", channel);
            Console.WriteLine("Done.");
        }
    }        
    private bool IsChannelInRange(int channel)
    {
        return (channel < 451) && (channel >= 0);
    }
    public bool IsValidInput(string input)
    {            
        int asInt = 0;
        return Int32.TryParse(input, out asInt) && IsChannelInRange(asInt);
    }        
}
class Program
{
    static void Main(string[] args)
    {
        RemoteControl rm = new RemoteControl();
        string input = "";
        bool turnOff = false;
        do
        {
            Console.Clear();
            Console.WriteLine("Enter a valid channel or '"off'" to turn off");
            input = Console.ReadLine();
            turnOff = input.ToLower() == "off";
        }
        while (!(turnOff || rm.IsValidInput(input)));
        if (!turnOff)
        {                
            rm.FindChannel(input.PadLeft(3,'0'));
            Console.ReadLine();
        }
    }
}