2

我最近接受了一次采访，被问到以下问题。

迷宫是一组链接的地方。每个地方都有与其相邻的北、南、东和西地方。有两个特殊的预定义 Place 的： Place Wall 代表一堵墙——鼠标不能去那里。地方奶酪是……奶酪！地方之间的连接是对称的——如果你从任何地方开始，然后向北走，然后向南走，你就会回到原来的地方。

为简化起见，迷宫没有闭环——也就是说，如果你从任何地方开始并沿着任何路径走，你最终要么撞到墙，要么找到奶酪——除非你真的回溯你的脚步，否则你永远不会回到你开始的地方.

一只老鼠从某个地方开始四处寻找奶酪。当它找到 Cheese 时，它​​会返回一组方向 - 一串字母 NSEW，从它开始的位置指向 Cheese。

以下框架定义了类和函数。此处未包含的其他一些代码通过创建一堆 Place 并链接它们来生成迷宫。然后它调用 mouse()，从迷宫中传递一些起始位置：

interface Place {

// Return the adjacent Place in the given direction
public Place goNorth();
public Place goSouth();
public Place goEast();
public Place goWest();

// Returns true only for the special "Wall" place
public bool isWall();

// Returns true only for the special "Cheese" place
public bool isCheese();
};

class Mouse {
  public Mouse() {}

  // Return a string of the letters NSEW which, if used to traverse the
  // the maze from startingPoint, will reach a Place where isCheese() is
  // true.  Return null if you can't find such a path.
  public String findCheese(Place startingPoint) {
    ... fill this in ...
  }
}

实现 findCheese()。您可以将所需的任何字段或辅助方法添加到鼠标。额外功劳：消除“无闭环”限制。也就是说，更改您的代码以使其正常工作，即使可能存在像 SSNEEW 这样的路径将鼠标引导回它开始的地方。

这是我尝试过的。我知道这不是最好的或优化的解决方案，我希望得到关于我还能尝试什么的反馈。我没有考虑额外的信用部分

public String findCheese(place startingPoint)
{
    //Call helper function in all 4 directions;
    return findCheeseHelper(startingPoint,new StringBuilder("N")).append(
        findCheeseHelper(startingPoint,new StringBuilder("S"))).append(
            findCheeseHelper(startingPoint,new StringBuilder("E"))).append(
                findCheeseHelper(startingPoint,new StringBuilder("W"))).toString();
}


public StringBuilder findCheeseHelper(place startingPoint, StringBuilder direction)
{
    StringBuilder nDir=new StringBuilder("");
    StringBuilder sDir=new StringBuilder("");
    StringBuilder eDir=new StringBuilder("");
    StringBuilder wDir=new StringBuilder("");

    //Rerturn which direction this step came from if cheese found
    if(startingPoint.isCheese())
    {
        return direction;
    }
    //Specify this is not a correct direction by returning an empty String
    else if(startingPoint.isWall())
    {
        return "";
    }

    //Explore all other 3 directions (except the one this step came from)
    if(direction=="N")
    {
        sDir=findCheeseHelper(startPoint.goSouth(), new StringBuilder("N"));
        eDir=findCheeseHelper(startPoint.goEast(), new StringBuilder("E"));
        wDir=findCheeseHelper(startPoint.goWest(), new StringBuilder("W"));
    }
    else if(direction=="E")
    {
        nDir=findCheeseHelper(startPoint.goNorth(), new StringBuilder("N"));
        sDir=findCheeseHelper(startPoint.goSouth(), new StringBuilder("S"));
        wDir=findCheeseHelper(startPoint.goWest(), new StringBuilder("E"));
    }
    else if(direction=="W")
    {
        nDir=findCheeseHelper(startPoint.goNorth(), new StringBuilder("N"));
        sDir=findCheeseHelper(startPoint.goSouth(), new StringBuilder("S"));
        eDir=findCheeseHelper(startPoint.goEast(), new StringBuilder("W"));
    }
    else if(direction=="S")
    {
        nDir=findCheeseHelper(startPoint.goNorth(), new StringBuilder("S"));
        eDir=findCheeseHelper(startPoint.goEast(), new StringBuilder("E"));
        wDir=findCheeseHelper(startPoint.goWest(), new StringBuilder("W"));
    }

    //If I hit wall in every direction, I will get empty string and so specify to calling 
    //function that this is not a correct direction
    if(nDir.equals("") && sDir.equals("") && eDir.equals("") && wDir.equals(""))
        return new StringBuilder("");

    //If Cheese was found in even 1 direction, return direction to come to this step, appended with the path
    // forward to the calling function
    return direction.append(nDir).append(sDir).append(eDir).append(wDir);
}
4

0 回答 0