2

Uber が主催する Codefights でコーディング チャレンジを行っていたのですが、解決できない問題がありました。質問については、こちらhttp://codepen.io/ducminhn/pen/JYmrmEを参照してください。

この問題は動的プログラミングに関連していると思われるので、この問題を動的プログラミングとしてタグ付けしましたが、私はまだ Java を学んでいるので、間違っていたらお知らせください。これは私がこれまでに持っているものであり、ネストされた for ループ内で私のロジックが正しくない可能性があると考えています。誰かが私のコードを見直して修正してください。

前もって感謝します、

boolean parkingSpot(int[] carDimensions, int[][] parkingLot, int[] luckySpot) {

int carx = carDimensions[0];
int cary = carDimensions[1];

boolean result = false;
for(int l=0;l<parkingLot.length;l++){
    for(int k=0;k<parkingLot.length;k++){
        if(l == luckySpot[0]){
            for(int i=luckySpot[0];i<carx;i++){
                if(k== luckySpot[1]){
                    for(int j= luckySpot[1];j<cary;j++){
                        if(parkingLot[i][j] != 0){
                            result = false;
                        }
                   }
                }
            }
        }
    }   
 }
 return true;
}
4

1 に答える 1

1

これはあなたがしたことよりも複雑に思えます...それが役立つかどうかはわかりません. 与えられた例に対してテストしただけですが、問題を完全に誤解していない場合は、いくつかのループを使用するだけでよいため、動的計画法を明確に使用することはできません。

    static boolean h(int[] luckySpot,int[][] parkingLot){
        // check if parking spot given contains a 1
        // (check if it's a valid parking spot)
        for(int i=luckySpot[0];i<=luckySpot[2];i++){
            for(int j=luckySpot[1];j<=luckySpot[3];j++){
                if(parkingLot[i][j]==1) return false;
            }
        }

        // check if the car parked vertically
        if(     Math.abs(luckySpot[0]-luckySpot[2]) > 
                Math.abs(luckySpot[1]-luckySpot[3])) {

            // check for empty path going to the top
            outerloop:
            for(int i=0;i<luckySpot[0];i++){
                for(int j=luckySpot[1];j<=luckySpot[3];j++){
                    if(parkingLot[i][j]==1) break outerloop;
                }
                if(i==luckySpot[0]-1) return true;
            }

            // check for empty path going to the bottom
            for(int i=luckySpot[2]+1;i<parkingLot.length;i++){
                for(int j=luckySpot[1];j<=luckySpot[3];j++){
                    if(parkingLot[i][j]==1) return false;
                }
                if(i==parkingLot.length-1) return true;
            }

        }
        // the car parked horizontally
        else{
            // check for empty path going to the left
            outerloop:
            for(int i=luckySpot[0];i<=luckySpot[2];i++){
                for(int j=0;j<luckySpot[1];j++){
                    if(parkingLot[i][j]==1) break outerloop;
                }
                if(i==luckySpot[2]) return true;
            }

            // check for empty path going to the right
            for(int i=luckySpot[0];i<=luckySpot[2];i++){
                for(int j=luckySpot[3]+1;j<parkingLot[0].length;j++){
                    if(parkingLot[i][j]==1) return false;
                }
                if(i==luckySpot[2]) return true;
            }

        }

        return false;
    }


    public static void main(String[] args) {

        /*
        "for safety reasons, the car can only move in two directions inside
        the parking lot -- forwards or backwards along the long side of the car"
        i assume this to mean that the direction the car travels is parallel
        to the long side of the car
         */


        int[] carDimensions = {3, 2};

        int [][] parkingLot = {
                {1, 0, 1, 0, 1, 0},
                {1, 0, 0, 0, 1, 0},
                {1, 0, 0, 0, 0, 1},
                {1, 0, 0, 0, 1, 1}
        };
        int[] luckySpot={1, 1, 2, 3};


        System.out.println(h(luckySpot,parkingLot));


    }
于 2016-09-06T13:39:53.240 に答える