Большая правительственная организация создала офис в Бангалоре. Офис был построен в прямоугольной форме, поэтому все его этажи также находятся в прямоугольной форме . Размер офиса - единицы X единиц x Y. Каждый этаж офиса имеет большую сидячую способность для своих сотрудников. Все каюты находятся в квадратной форме. Таким образом, площадь каждого этажа разделена на каюты X * Y размером 1 единица х 1 единицы.Минимальная стоимость подключения некоторых кают
См. Диаграмму, приведенную в качестве примера.
Здесь, в изображении выше,
P означает, что сотрудники могут передать свои файлы друг другу
NP означает, что сотрудники не могут передать свои файлы друг другу
Как показано в приведенном выше примере, размер пола составляет 4 единицы x 5 единиц, а на полу есть 4 * 5 = 20 кают, 1 единица х 1 каюты. Некоторые из кают имеют хорошо прикреплены друг к другу, а некоторые нет. Каюты, которые хорошо связаны друг с другом, прохождение файлов в этих каютах очень просто. Другие кабины , которые плохо связаны друг с другом, передача файлов в этих каютах невозможна. Каюты показаны на приведенном выше рисунке с метками P и NP соответственно.
Таким образом, кабина в (3, 1) может передавать файлы по (2, 1), (1, 1), (1, 2), (2, 2) и (4, 2). Все эти прилагаемые части кумулятивно образуют полную проходную область. Следовательно, весь пол разделен на различные П-регионы из-за отсутствия проходных кают.
Как и в приведенном выше примере, у нас есть две P-области одна слева и одна справа. Организация может исправить положение кабины в NP-регионах, но может привести к некоторой стоимости, и каждая кабина NP может иметь разную стоимость. Фактически, нет необходимости корректировать кабины NP, потому что их работа очень различна. Задача организации заключается в подключении различных областей P. Это возможно, если некоторые из кабин NP превращены в кабины P. Таким образом, сложная задача для организации заключается в том, что она хочет организовать эти каюты как можно меньше.
Левая фигура представляет ситуацию кабины, будь то Р или NP. Правая фигура имеет какое-то значение, записанное в каждой каюте, и это стоимость, требуемая для , организует каюты в полу. Как показано на рисунке, каждая кабина P имеет стоимость -1, это означает, что для организации этих кают не требуется никаких затрат. Но для в каждой кабине NP есть некоторая положительная стоимость. В этом примере есть четыре области P, все P-регионы состоят всего из 1 кабины. Задача для организации состоит в том, чтобы соединить все четыре P-области (что тоже по наименьшей возможной цене).
Это может быть сделано различными способами; два возможных способа являются следующим образом-
Стоимость для метода 1 является 10 + 10 + 10 = 30
Стоимость для метода 2 только 2
Так что, если мы организуем кабины NP со стоимостью 2, он соединит все четыре разных кабины P. И для приведенного выше примера это наименьшая возможная стоимость. Вы должны вернуть минимально возможную стоимость, в которой все каюты P могут быть прикреплены друг к другу.
Выходные характеристики:
Это целое число, которое определяет минимальную возможную стоимость, в которой все каюты P могут быть прикреплены друг к другу
или
возврата 0, если все P каюты уже прикреплены друг к другу или, если нет P кабины
Моего кода: -
class Code {
public int[][] array;
boolean flag=true;
int[][] a;
int R;
int C;
int MAX=2147483647;
LinkedList l=new LinkedList();
void initialize() {
R=array.length;
C=array[0].length;
a=new int[R][C];
for(int i=0;i<R && flag;i++) {
for(int j=0;j<C && flag;j++) {
if(array[i][j]==-1) {
flag=false;
}
}
}
}
void process() {
int p=0,q=0;
for(int i=R-1;i>=0;i--) {
for(int j=C-1;j>=0;j--){
if(array[i][j]==-1) {
p=i;
q=j;
array[i][j]=0;
}
a[i][j]=MAX;
}
}
l.add(p);
l.add(q);
a[p][q]=0;
}
void solve() {
int p=0,q=0;
while(l.size()>0) {
p=(int)l.removeFirst();
q=(int)l.removeFirst();
for(int i=p-1;i<=p+1;i++) {
for(int j=q-1;j<=q+1;j++){
if(i>=0 && j>=0 && i<R && j<C && a[i][j]>a[p][q]+array[i][j]) {
a[i][j]=a[p][q]+array[i][j];
l.add(i);
l.add(j);
}
}
}
}
}
public int minimumcost() {
initialize();
if(flag)
return 0;
process();
solve();
MAX=0;
for(int i=0;i<R;i++) {
for(int j=0;j<C;j++){
if(array[i][j]==0 && a[i][j]>MAX)
MAX=a[i][j];
}
}
return MAX;
}
}
Здесь массив - это массив, а minimumcost - это функция, возвращающая ответ. Из 10 тестовых случаев 5 были правильными. Я не могу найти ошибку.
В моем коде я сначала проверил, была ли по крайней мере одна каюта с P. Из любого одного PPI проходили по всем направлениям (все соседи), используя связанный список (используемый здесь в качестве очереди), отслеживая минимум, чтобы достичь этого клетка. В итоге я нашел максимальное значение.
Так почему же этот Q получает отрицательные оценки, но никто не хочет комментировать его? Помогите этому парню понять, что он делает не так ;-) – JayC667
Действительно ли ваше НАЧАЛЬНОЕ домашнее задание действительно необходимо для понимания проблемы с вашим кодом? Подкрепляет вас для фактического размещения кода, но этот вопрос лениво сложен.Вы должны иметь некоторое отношение к людям, которые действительно читают это, и приложить больше усилий для упрощения того, что вы пытаетесь сделать. – tnw
@tnw Это не вопрос домашней работы. Это было задано в тесте на подбор персонала. Этот вопрос был более подробным, чем сейчас, но я удалил любую часть, которую я мог бы удалить, чтобы сократить ее. Эта подробная информация была необходима для правильного понимания. И для моего кода это в основном не так запутанно, если вы пытаетесь прочитать, хотя я добавил свой подход сейчас в конце текста. –