0

大企業の面接でこんな質問を受けました。

このインターフェースがあるとしましょう：

interface ILabyrinth
{

   // create a labyrinth of size 100*100 max.  Rabbit and carrot are positioned at random locations within the maze.
   void Init();

   // try to move the rabbit in one direction.  return true if the move was successful, returns false otherwise (there was a wall) 
   bool tryMove(Direction d);

   // return true if carrot and rabbit are at the same place.
   bool isSuccess();

}

ニンジンを見つけるためにウサギをどのように動かしますか? 到達したら停止するだけです。

私の解決策は、tryMove() 関数を使用してマウスをバックトラックする必要があることを除いて、従来の DFS 検索を適用することです。

そして、サイズ 198*198 ( = (100-1)*2) の新しいマップでウサギの動きを追跡することによってそれを行います。この地図では、私たちがその位置に来たときの方向を保存しています。簡単に後戻りできるので。

それを改善する方法はありますか？

4

2 に答える 2

0

これがインタビューだった場合、「マウスとチーズ」が「ウサギとニンジン」になり、細部のように見えますが、意図的に作成されている可能性があることに言及していただければ幸いです... (そして、移動しただけでは isSuccess() は true を返しません)ねずみであってうさぎではない!)

それとは別に、私は DFS を使用しませんでしたが、POI がどこにあるかわからないため、より深く (BFS) に進む前に、利用可能なブランチごとに 1 つのケースを移動しました。新しい距離が以前の距離よりも短い場合を除いて、ノードへの訪問を禁止します (ただし、頻繁に発生するわけではありません!)。後退しないこと (右に移動したときに左に移動すること) はプラスですが、前のルールに含まれます。

とにかくうまくいくことを願っています... GL！

編集: 私はこれを見つけました: http://www.astrolog.org/labyrnth/algrithm.htm#solve . ここで私がぎこちなく提案したのは、人間が怖がらないsjortestパスに対応しており、距離のある* nグリッドを使用してローカルに迷路を再作成します（説明されている2番目の最短パスだと思います...）

ところで、ここでの質問は何でしたか: ニンジンを見つけること? それへの最短経路を見つけますか？パスをたどるかどうか???

再編集: あいまいさを解消した後、この回答の一部は問題に適合しません: 目的は最短経路ではなくニンジンであり、ウサギは一度に 1 つの正方形にしか入ることができません。

于 2013-04-29T11:22:53.507 に答える