Функция парковочного места с учетом массива парковки и габаритов автомобиля
Я выполнял задачи по кодированию на Codefights, спонсируемые Uber, и была проблема, которую я не смог решить. По вопросу, вы можете посмотреть здесь 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;
}
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));
}