1

私は迷路を与えられ、道を見つけようとするプログラムを書こうとしています。Mは入口、Eは出口、1は壁、0は通路です。各パスを見つけて、パスにPを入れることになっています。利用可能なすべてのパスを見つけることになっています。現在、パスの一部が見つかります。

コードは次のとおりです。

public class Maze 
{
    private int size;
    private String[][] board;
    private int total; //# of boards
    private int eX;
    private int eY;
    private int mX;
    private int mY;

    public Maze( int size, String[][] board )
    {
        this.size = size;
        this.board = board;
        total = 0;

    }

    private void find( String c )
    {
        int x=0, y=0;
        for( int i = 0; i < size; i++ )
        {
            for( int j = 0; j < size; j++ )
            {
                if( board[i][j].equals(c) )
                {
                    x = i;
                    y = j;
                }
            }
        }
        if( c.equals("M") )
        {
            mX = x;
            mY = y;
        }
        else if( c.equals("E") )
        {
            eX = x;
            eY = y;
        }
    }

    public void findPath(  )
    {
        find( "M" );
        find( "E" );
        findNext( mX, mY );
    }

    public void findNext( int x, int y )
    { 
        String last = board[x][y];
            if( board[x][y].equals("P") ) board[x][y] = "1";
        board[x][y] = "P";

        if( rightAvailability(x,y) )
        {
            findNext(x+1, y);
        }
        else if( leftAvailability(x,y) )
        {
            findNext(x-1, y);
        }
        else if( aboveAvailability(x,y) )
        {
            findNext(x, y+1);
        }
        else if( belowAvailability(x,y) )
        {
            findNext(x, y-1);
        }
        else
        {
            total++;
            printBoard();
        }

        board[x][y]= last;
    }

    public boolean rightAvailability( int x, int y )
    {
        if( x+1 >= size ) return false;
        else if( board[x+1][y].equals("1") ) return false;
        else if( board[x+1][y].equals("P") ) return false;
        else return true;
    }
    public boolean leftAvailability( int x, int y )
    {
        if( x-1 < 0) return false;
        else if( board[x-1][y].equals("1") ) return false;
        else if( board[x-1][y].equals("P") ) return false;
        else return true;
    }
    public boolean aboveAvailability( int x, int y )
    {
        if( y+1 >= size ) return false;
        else if( board[x][y+1].equals("1") ) return false;
        else if( board[x][y+1].equals("P") ) return false;
        else return true;
    }
    public boolean belowAvailability( int x, int y )
    {
        if( y-1 < 0) return false;
        else if( board[x][y-1].equals("1") ) return false;
        else if( board[x][y-1].equals("P") ) return false;
        else return true;
    }

    public void printBoard()
    {
        System.out.println( "The board number " +total+ " is: ");
        for(int i=0; i< size; i++ )
        {
            for(int j=0; j< size; j++ )
            {
                if( (i==mX) && (j==mY) )
                {
                    System.out.print("M");
                }
                else if( (i==eX) && (j==eY) )
                {
                    System.out.print("E");
                }
                else if( board[i][j].equals("1") )
                {
                    System.out.print("1");
                }
                else if( board[i][j].equals("0") )
                {
                    System.out.print("0");
                }
                else
                {
                    System.out.print("P");
                }
            }
            System.out.println();
        }
    }
}

テスターは次のとおりです。

public class MazeTester 
{
    public static void main(String[] args) 
    {
        int size = 11;
        String[][] board = new String[][]
            {
                {"1","1","1","1","1","1","1","1","1","1","1"},
                {"1","0","0","0","0","0","1","0","0","0","1"},
                {"1","0","1","0","0","0","1","0","1","0","1"},
                {"E","0","1","0","0","0","0","0","1","0","1"},
                {"1","0","1","1","1","1","1","0","1","0","1"},
                {"1","0","1","0","1","0","0","0","1","0","1"},      
                {"1","0","0","0","1","0","1","0","0","0","1"},
                {"1","1","1","1","1","0","1","0","0","0","1"},
                {"1","0","1","M","1","0","1","0","0","0","1"},
                {"1","0","0","0","0","0","1","0","0","0","1"},
                {"1","1","1","1","1","1","1","1","1","1","1"},  
            };


        Maze m = new Maze( size, board );
        m.findPath();
    }
}

現在の出力は次のとおりです。

The board number 1 is: 
11111111111
1PPPPP1PPP1
1P1PPP1P1P1
EP1PPPPP1P1
101111101P1
10101PPP1P1
10001P1PPP1
11111P1PP01
101M1P1PP01
100PPP1PP01
11111111111
The board number 2 is: 
11111111111
1PPPPP1PPP1
1P1PPP1P1P1
EP100PPP1P1
101111101P1
10101PPP1P1
10001P1PPP1
11111P1PP01
101M1P1PP01
100PPP1PP01
11111111111
The board number 348 is: 
11111111111
1PPPPP10001
1P1PPP10101
EP1PPPPP101
1011111P101
10101PPP101
10001P10001
11111P10001
101M1P10001
100PPP10001
11111111111

編集：if（board [x] [y] .equals（ "P"））board [x] [y] = "1"; findIndexの先頭。x<=0の問題も修正しました。出力を現在取得しているものに更新しました（実際には348枚の同様のボードを印刷しています）。

4

2 に答える 2

1

標準のパスファインディングアルゴリズムが機能するはずです。ワールド定義に一致するようにそれらを変更する必要があります。

しかし、A*またはD*アルゴリズムはかなりうまく機能します。彼らはあなたがあなたの世界の定義から定義することができるはずのグラフを使用します。（http://en.wikipedia.org/wiki/A *）

また、Dijstraのアルゴリズムは、パスを見つける際に機能するはずです（ここでもグラフを使用します）。これは一般的にネットワークルーティングに使用されますが、通常のパスファインディングにも機能します。（http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm）

基本的に私のアプローチは、迷路の定義をグラフに変換し（ノードは「結合点」、エッジは「廊下」）、それらのアルゴリズムの1つを使用することです。

于 2009-10-06T05:04:12.990 に答える
1

私は部分的な推測を行に置きました：

else if( belowAvailability(x,y) )
{
        findNext(x, x-1);
}

x-1はy-1である必要があります

あなたが見つけるもう一つの問題は、あなたがelseifブロックを使用しているという事実にあります。ブランチに遭遇した場合は、

1E1
101
1P0
1P1

あなたは最初に正しく行こうとします、そしてそれが惨めに失敗したとき、それは上がろうとはしません。実際にテスト出力でそれを見ることができます、

_._._789_._
_..._6_A54_
_____5_B23_
_._M_4_C10_
_..123_DEF_
___________

読みやすいように16進数で番号が付けられています。右下隅に入り、スタックします。ボードを移動する場所が他にない場合は印刷され、再帰はテストされていない正方形へのバックトラックなしで終了します。

もう一度編集します。まだ探していますが、左/右の可用性には別のx / yの不一致があり、おそらくx-1 <0（またはy-1）の場合にのみ可用性を拒否する必要があります。ゴールノードはy=0にあるため。

これらの変更と、x == eX && y == eYの場合にのみ印刷トリガーを使用すると、ソリューションの出力が得られます。非常に多くの解決策ですが、解決策です。

編集カウントに関するもう1つのユーモラスな事実：あなたは左/右と上/下を後方に持っています。x座標は、表示している入力の行を指定し、y座標は列を指定します。このような場合にr/cを使用することはかなり一般的です。

于 2009-10-06T02:34:29.797 に答える