Ska traversera så många celler som möjligt
Har en programmerings uppgift som jag inte är helt säker på hur jag ska börja med. Jag skapar ett rutnät med hjälp av en 2D array, så varje kolumn och rad bildar tillsammans en koordinat. I rutnätet kommer vissa celler vara "förbjudna att besöka". Sedan ska en orm(snake) börja på position 0,0 och traversera så många celler som möjligt, utan att besöka de förbjudna cellerna. Output ska vara antalet celler som är besöka samt rätt ordning på traverseringen. Här är en bild för all illustrera vad som menas: https://imgur.com/a/qzxZv
Min initiala tanke var att detta kan ju liknas med en graf och att jag bör använda depth eller breadth first traversering på något sätt, men jag är inte säker. Hade varit uppskattat om någon kunde ge mig lite idéer på vad jag skulle kunna göra. Har lekt runt lite med stack och queue också, men inte helt säker på vad implementationen blir. För tillfället har jag kod som traverserar alla celler i ordning, bara för att börja någonstans.
private void testRun() {
System.out.println("Beginning testRun");
Stack stack = new Stack();
ArrayList<String> result = new ArrayList<String>();
// Each column
for (int i = 0; i < brickArray.length; i++) {
// Each row
for (int j = 0; j < brickArray[i].length; j++) {
Brick tempBrick = brickArray[i][j];
if (!tempBrick.isVisited() && !tempBrick.isObstacle()) {
brickArray[i][j].setVisited();
result.add(i + "," + j);
stack.push(String.valueOf(i) + "," + String.valueOf(j));
}
}
}
System.out.println(result.size());
System.out.println(result);
System.out.println("Stack " + stack);
}
Output:
13
[0,0, 0,1, 0,2, 0,3, 1,0, 1,3, 2,0, 2,1, 2,3, 3,0, 3,1, 3,2, 3,3]