题解 | #跳石板#

using System;
using System.Collections;
using System.Collections.Generic;
public class Program
{
  //取得num的因数，装在stack中
    public static void div(int num, Stack<int> stack)
    {
        stack.Clear();
        double temp = Math.Sqrt(num);
        for (int i = 2; i <= temp; i++)
        {
            if(num % i == 0 && i == temp)
            {
                stack.Push(i);
            }
            else if(num % i == 0)
            {
                stack.Push(i);
                stack.Push(num / i);
            }
        }
    }
    public static void Main()
    {
        string line;
        while ((line = Console.ReadLine()) != null)
        { // 注意 while 处理多个 case
            string[] tokens = line.Split(' ');
            int n = int.Parse(tokens[0]);
            int m = int.Parse(tokens[1]);
            //BFS
            int[] ans = new int[m + 1]; //ans[x]代表到达x需要最少需要多少步
            ArrayList.Repeat(int.MaxValue, m + 1).CopyTo(ans);
            ans[n] = 0;
            //从n出发，遍历每个当前数可以到达的数，若该数未到达过，ans[stack.Peek()] =ans[i] + 1，到达过则比较大小，选小的赋值
            Stack<int> s = new Stack<int>();//用来装因数
            Queue<int> q = new Queue<int>();//用来做BFS
            q.Enqueue(n);
            while (q.Count != 0)
            {
                int i = q.Dequeue();
                div(i, s);
                while (s.Count != 0)
                {
                    int j = s.Pop();
                    if (i + j > m) continue;
                    if (ans[i + j] == int.MaxValue)//未访问过该点
                    {
                        ans[i + j] = ans[i] + 1;
                        q.Enqueue(i + j);
                    }
                    else
                    {
                        if (ans[i + j] > ans[i] + 1) ans[i + j] = ans[i] + 1;
                    }
                }
            }
            if (ans[m] == int.MaxValue) ans[m] = -1;//若m未访问到则赋值-1
            Console.WriteLine(ans[m]);
        }
        
    }
}

用BFS来做