5

ロボットは 4x4 グリッドの左上隅にあります。ロボットは上下左右に移動できますが、同じ場所を 2 回訪れることはできません。ロボットはグリッドの右下隅に到達しようとしています.グリッドの右下隅に到達できる方法の数は?

これで、ロボットが下または右にしか移動できない場合、答えは 8C4 になることがわかりました。これは、右に 4 マス、下に 4 マス移動する必要があるためです。

しかし、ロボットが上下左右に動くと、問題を解決するのに苦労します!?

問題を解決するためのヒントが必要です。問題にどのようにアプローチすればよいですか？

4

4 に答える 4

0 
/* building on red_eyes answer */

public static void main(String[] args) {
    Main m = new Main();
    boolean grid [][]= new boolean [4][4];
    sol=0;
    grid[0][0]= true;
    m.start(0,1,grid);
    System.out.println(sol);//output 184
}

    private void start(int x, int y,boolean [][]grid){
    grid[x][y]=true;
    moveUp(x,y,grid);
    moveDown(x,y,grid);     
    moveLeft(x,y,grid);     
    moveRight(x,y,grid);         
}

private void moveUp(int x, int y, boolean [][] grid){
    if(y==0) return;
    else{
        if (grid[x][y-1]) return;
        grid[x][y-1]=true;
        start(x,y-1,grid);
        grid[x][y-1]=false;
    }
}
   private void moveLeft(int x, int y, boolean [][] grid){
    if(x==0) return;
    else{
        if (grid[x-1][y]) return;
        grid[x-1][y]=true;
        start(x-1,y,grid);
        grid[x-1][y]=false; 
    }
}
private void moveDown(int x, int y, boolean [][] grid){
    if(x==3 && y==3){
        sol++;
        grid[x][y]=true;
        return;
    }
    else if(y==3) return;
    else{
        if (grid[x][y+1]) return;
        grid[x][y+1]=true;
        start(x,y+1,grid);
        grid[x][y+1]=false;
    }
}


private void moveRight(int x, int y, boolean [][] grid){
    if(x==3 && y==3){
        sol++;
        grid[x][y]=true;
        return;
    }else if(x==3) return;
    else{
        if (grid[x+1][y]) return;
        grid[x+1][y]=true;
        start(x+1,y,grid);
        grid[x+1][y]=false; 
    }
}
于 2014-02-17T17:38:45.227 に答える