Full kode finner du her.
Main metode
For alle oppgavene i 2024 bruker jeg Java, og dette vil være metoden jeg bruker for å hente input for de ulike oppgavene. Input blir lagret i en txt fil og hentes via denne metoden.
Oppgave 1
Luke 18 går ut på å navigere seg fremover i en grid fra nordvest hjørne til sørøst hjørne gitt at X antall bokser er blitt fylt med blokader. Vi ønsker å finne minste antall steg for å komme oss ut. Først må vi simulere hvor brikkene skal lande, og så finne korteste vei til mål. For å finne korteste sti valgte jeg å kjøre en Breadth First Search (BFS) algoritme. Denne algoritmen er en av de enkleste algoritmene for å finne korteste vei i en graf. Algoritmen fungerer ved å utforske alle naboer til en node før den går videre til neste nivå av naboer. Metoden ble da slik:
private static int bfs(char[][] maze, int[] start, int[] end) {
int[] dx = {0, 1, 0, -1};
int[] dy = {1, 0, -1, 0};
PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(a -> a[2]));
boolean[][][] visited = new boolean[maze.length][maze[0].length][4];
queue.add(new int[]{start[0], start[1], 0, 0});
while (!queue.isEmpty()) {
int[] current = queue.poll();
int x = current[0];
int y = current[1];
int cost = current[2];
if (x == end[0] && y == end[1]) return cost;
for (int newDir = 0; newDir < 4; newDir++) {
int nx = x + dx[newDir];
int ny = y + dy[newDir];
if (isValid(maze, nx, ny) && !visited[nx][ny][newDir]) {
visited[nx][ny][newDir] = true;
int newCost = cost + 1;
queue.add(new int[]{nx, ny, newCost, newDir});
}
}
}
return -1;
}
private static boolean isValid(char[][] maze, int x, int y) {
return x >= 0 && x < maze.length && y >= 0 && y < maze[0].length && maze[x][y] != '#';
}
Oppgave 2
For oppgave 2 ønsker vi enkelt å greit å finne når det ikke lengre er mulig å komme seg ut av labyrinten. Vi ønsker å finne antall steg før vi er fanget. Dette kan gjøres ved å kjøre samme metode som i oppgave 1 og sjekke for alle etter 1024. Metoden ble slik:
private static int search(char[][] maze, int[] start, int[] end, List<String> lines){
int num = 1024;
int size = lines.size() - 1;
while (num <= size){
num++;
int x = parseInt(lines.get(num).split(",")[0]);
int y = parseInt(lines.get(num).split(",")[1]);
maze[y][x] = '#';
int cost = bfs(maze, start, end);
if(cost == -1) break;
}
return num;
}