如何看待卡蒂斯问题:电梯问题?

Question

我一直在尝试解决卡蒂斯的问题& "电梯故障& ";在c# https://open.kattis.com/problems/elevatortrouble工作了一段时间但是我总是漏掉一些东西，因为我从来没有通过我的解决方案中的所有测试。

给出测试用例(并成功执行)

输入:10 1 10 2 1，我的输出:6，期望输出:6

输入:100 2 1 10，我的输出:使用楼梯，期望输出:使用楼梯

在Kattis问题中提供的测试用例通过了(见上文)，并给出了预期的输出

这是最成功的解决方案:

class Program
{
static void Main(string[] args)
{
var input = Console.ReadLine();
var values = input.Split(" ");
var output = NumberOfButtonPress(values);
Console.WriteLine(output);
}
public static string NumberOfButtonPress(string[] values)
{
int floors = int.Parse(values[0]);
int start = int.Parse(values[1]);
int goal = int.Parse(values[2]);
int up = int.Parse(values[3]);
int down = int.Parse(values[4]);
var buttonPresses = goal - (start + (up * up) - (down * down)); 
return buttonPresses >= 0 && buttonPresses < floors ? buttonPresses.ToString() : "use the stairs";
}
}

Answer 1

这个问题比一个简单的上、下、上、下或下、上、下的集合稍微复杂一点。

第一步

用给定的参数检查是否可行，

第二步:

find the algorithm.

仅仅因为当前阶段低于目标并不意味着最好的解决方案是按向上键开始

编辑在https://open.kattis.com/

上验证的解决方案存在使用width -firstrongearch或BFS算法的解决方案:目标是探索所有可能性(以避免无限循环)并查看解决方案是否存在。(可能不是最好的解决方案)

using System;
using System.Collections.Generic;
using System.Linq;
namespace ConsoleApp2
{
public class Program
{
public static int f;
public static int s;
public static int g;
public static int u;
public static int d;
static void Main(string[] args)
{
string line;
while ((line = Console.ReadLine()) != null)
{
string[] values = line.Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
if (values.Length != 5 || values.Any(x => !int.TryParse(x, out int value)))
continue;
var intgs = values.Select(int.Parse).ToArray();
if (!intgs.All(x => x >= 0 && x <= 1000000))
continue;
if (intgs[1] > intgs[0] ||
intgs[2] > intgs[0] || 
intgs[1] < 1 || intgs[2] < 1)
continue;
f = intgs[0];
s = intgs[1];
g = intgs[2];
u = intgs[3];
d = intgs[4];
var result = NumberOfButtonPress();
Console.WriteLine(result);
}
}
public static string NumberOfButtonPress()
{
var result = BFS();
if (result < 0)
return "use the stairs";
else
return ($"{result}");
}
private static int BFS()
{
Queue<(int, int)> q = new Queue<(int, int)>();
HashSet<int> seen = new HashSet<int>();
Action<int, int, int> move = (int currFloor, int numSteps, int location) =>
{
int nextFloor = currFloor + location;
if (!seen.Contains(nextFloor))
{
q.Enqueue((nextFloor, numSteps + 1));
seen.Add(nextFloor);
}
};
q.Enqueue((s, 0));
seen.Add(s);
while (q.Count > 0)
{
(int currFloor, int numSteps) = q.Dequeue();
if (currFloor == g)
{
return numSteps;
}
if (u + currFloor <= g)
move(currFloor, numSteps, u);
else if (currFloor - d >= 1)
move(currFloor, numSteps, -d);
}
return -1;
}
}
}