Так что, практикуя на USACO, я застрял в этом вопросе.Генерировать состояния для первого поиска глубины
Вопрос: В комнате есть N ламп (все изначально включены). Есть 4 переключателей для ламп с каждым переключателем переключает конкретные лампы, как:
Switch 1 : Toggles all the lamps
Switch 2 : Toggles all ordered numbered lamps
Switch 3 : Toggles all even numbered lamps
Switch 4 : Toggles all numbers that have modulus 1 with 3 (1, 4, 9)
числа С поставляются, который представляет собой общее количество переключателей клавиша. Первоначально все лампы включены. Также приводятся состояния некоторых из ламп в конечных состояниях.
Задача состоит в том, чтобы перечислить все возможные конечные состояния, в которых могут быть луковицы.
Для этого я придумал решение, основанное на Depth First Search. Я представляю каждую луковицу на элемент в массиве и луковице я включен, если если массив [я-1] является 1, если от массива [я-1] = 0. Вот мой код
/**
* Created by hp on 21-05-2015.
*/
import java.util.*;
public class lamps {
public static void main(String[] args) {
Scanner myScanner = new Scanner(System.in);
int numLamps = myScanner.nextInt();
int[] startState = new int[numLamps];
for(int i = 0; i < numLamps; i++){
startState[i] = 1;
}
int numSwitchPressed = myScanner.nextInt();
int[] finalState = new int[numLamps];
/*
-1 represents the lamp's state in the final state,
whose state is not stated , can be both on and off
*/
for(int i = 0; i < numLamps; i++){
finalState[i] = -1;
}
/*
ON Lamps in the final state
*/
int on = myScanner.nextInt();
while(on != -1){
finalState[on-1] = 1;
on = myScanner.nextInt();
}
/*
OFF Lamps in the final state
*/
int off = myScanner.nextInt();
while(off != -1){
finalState[off-1] = 0;
off = myScanner.nextInt();
}
//TESTING THE GENERATE STATES METHOD HERE
ArrayList<int[]> nextStates = nextStates(startState);
for(int[] x: nextStates){
for(int y: x){
System.out.print(y + " ");
}
System.out.println();
}
System.out.println("========================================");
System.out.println("========================================");
callSearch(finalState, numSwitchPressed);
}
/*
Generate the states that are results of pressing each switch
Switch 1 : Toggle all
Switch 2 : Toggle odd numbered lamps(effectively indices 0,2,4,6,)
Switch 3 : Toggle even numbered lamps(effectively indices 1, 3, 5, 7)
Switch 4 : Toggle lamps numbered 3x+1 (1, 4, 7, 10, 13)
*/
public static ArrayList<int[]> nextStates(int[] presentState){
int len = presentState.length;
ArrayList<int[]> nextState = new ArrayList<int[]>();
int[] switchOne = new int[len];
int[] switchTwo = new int[len];
int[] switchThree = new int[len];
int[] switchFour = new int[len];
// Switch One : Toggle All
for(int i = 0; i < len; i++){
switchOne[i] = 1 - presentState[i];
}
nextState.add(switchOne);
//Switch Two : Toggle odd numbered lamps
for(int i = 0; i < len; i++){
if(i % 2 == 0){
switchTwo[i] = 1 - presentState[i];
}
else{
switchTwo[i] = presentState[i];
}
}
nextState.add(switchTwo);
// Switch Three : Toggle even numbered lamps
// 1, 3, 5, 7 , 9
for(int i = 0; i < len; i++){
if(i % 2 != 0){
switchThree[i] = 1 - presentState[i];
}
else{
switchThree[i] = presentState[i];
}
}
nextState.add(switchThree);
// Switch four : Toggle 1, 4, 7, 10
for(int i = 0; i < len; i++){
if(i % 3 == 1){
switchFour[i] = 1 - presentState[i];
}
else{
switchFour[i] = presentState[i];
}
}
nextState.add(switchFour);
return nextState;
}
/*
def searchFinal (cntSoFar, FixedCnt, currentState, FinalState):
if cntSoFar == FixedCnt:
if currentState == FinalState:
print currentState
return
return
ListOfNextStates = generatenextState(currentState)
for each new_state in ListOfNextStates:
searchFinal(cntSoFar+1, FixedCnt, new_state, FinalState)
*/
public static void searchFinal(int cntSoFar, int FixedCnt, int[] currentState, int[] finalState){
if(cntSoFar == FixedCnt){
if(same(currentState, finalState)){
for(int i = 0; i < finalState.length; i++){
System.out.print(currentState[i] + " ");
}
System.out.println();
return;
}
return;
}
ArrayList<int[]> nextStates = nextStates(currentState);
for(int[] states: nextStates){
searchFinal(cntSoFar+1, FixedCnt, states, finalState);
}
}
/*
WRAPPER METHOD FOR searchFinal
*/
public static void callSearch(int[] finalState, int FixedCnt){
int len = finalState.length;
int[] start = new int[len];
for(int i = 0; i < len; i++)
start[i] = 1;
ArrayList<int[]> firstCandidates = nextStates(start);
for(int[] state: firstCandidates){
searchFinal(0, FixedCnt, state, finalState);
}
}
public static boolean same(int[] currentState, int[] finalState){
int len = finalState.length;
for(int i = 0; i < len; i++){
if(finalState[i] != -1){
if(currentState[i] != finalState[i])
return false;
}
}
return true;
}
}
Как вы можете см. Я создаю следующие состояния в методе nextState. Проверка того, что требования конечного состояния удовлетворяются одним и тем же способом.
Мой вопрос (извините за длинный контекст): если начальное состояние лампы 1111111111 (скажем, 10 ламп, все включено), а c равно 1 (допустимо количество нажатий на выключатели), тогда есть только четыре состояния поиск, а именно:
- 0000000000 (Переключатель 1 нажата)
- 0101010101 (Переключатель 2 нажата)
- 1010101010 (Переключатель 3 нажата)
- 0111011101 (Переключатель 4 нажата)
Состояние последнего состояния заключается в том, что лампа 7 должна быть выключена. (Мы не заботимся о каких-либо других лампах) Таким образом, ответ должен быть
0000000000 (All are off)
0101010101 (1,3,5,7,9 are off)
Но грейдер показывает ответ как
0000000000
0101010101
0110110110
ВОПРОС: Третье состояние грейдер ответ, где сделал это исходит? Я имею в виду, так как c равно 1 (разрешенное число нажатых кнопок), единственными возможными состояниями ламп являются перечисленные выше 4. Как возможно 3-е состояние ламп, упомянутых в грейдерском ответе?
Ссылка на сообщение о проблеме, пожалуйста. – taufique
Определите 'упорядоченный номер *! – fabian
Если номера ламп начинаются с 1, нажатие четвертого переключателя приведет к последнему результату. также нажатие 4.-го переключателя, конечно, не приведет к результату '0111011101', даже если вы начнете использовать номера ламп в 0. – fabian