Brut force pour la partie 2

Pour la partie 1 , j'ai appliqué un bête parcours en profondeur.
Pour la partie 2, j'ai laissé tourner ma solution de partie 1 pour trouver la max de la partie 2.
Environ 1h de calcul.

J'aurai bien essayé de faire un truc plus intelligent mais je n'avais pas le temps.

Il faut quand même lancer ce code -Xss1g pour avoir une stack conséquence qui permet une récursivité aussi profonde.

package aoc2023;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Aoc2023s23 {
 public static Point[] DIRECTIONS = new Point[] { new Point(1, 0), new Point(-1, 0), new Point(0, -1),
 new Point(0, 1) };
 public record Point(int x, int y) {
 }
 public static class Path {
 boolean[][] walked;
 int[] pathX;
 int[] pathY;
 int step = -1;
 public Path(World world) {
 walked = new boolean[world.height][world.width];
 this.pathX = new int[world.width * world.height];
 this.pathY = new int[world.width * world.height];
 }
 public void move(int x, int y) {
 walked[y][x] = true;
 step++;
 this.pathX[step] = x;
 this.pathY[step] = y;
 }
 public void back() {
 if (step >= 0) {
 int x = getX();
 int y = getY();
 walked[y][x] = false;
 }
 step--;
 }
 private int getY() {
 return this.pathY[step];
 }
 private int getX() {
 return this.pathX[step];
 }
 }
 public static class World {
 List<String> rows;
 int width;
 int height;
 int endx;
 int endy;
 int maxPath =0;
 public World(List<String> rows) {
 this.rows = rows;
 this.height = rows.size();
 this.width = rows.get(0).length();
 this.endx = width - 2;
 this.endy = height - 1;
 }
 public final char cell(int x, int y) {
 return rows.get(y).charAt(x);
 }
 public boolean canWalkFrom(int sx, int sy, int dx, int dy) {
 if (dx < 0 || dx >= width || dy < 0 || dy >= height) {
 return false;
 }
 char dest = cell(dx, dy);
 if (dest == '#') {
 return false;
 }
 char start = cell(sx, sy);
 return true;
 /*
 if (start == '.') {
 return true;
 } else if (start == '>') {
 return dx > sx;
 } else if (start == '<') {
 return dx < sx;
 } else if (start == '^') {
 return dy < sy;
 } else if (start == 'v') {
 return dy > sy;
 }
 throw new RuntimeException("Unsupported " + start);
 */
 }
 public void explore(Path path) {
 int sx = path.getX();
 int sy = path.getY();
 if(sx == endx && sy == endy) {
 System.out.println("Size:" + path.step);
 if(path.step > maxPath ) {
 maxPath = path.step;
 }
 return ;
 }
 for (int i = 0; i < DIRECTIONS.length; i++) {
 Point p = DIRECTIONS[i];
 int dx = sx + p.x;
 int dy = sy + p.y;
 if (canWalkFrom(sx, sy, dx, dy) && !path.walked[dy][dx]) {
 path.move(dx, dy);
 explore(path);
 path.back();
 }
 }
 }
 }
 public static void main(String[] args) {
 try (Scanner in = new Scanner(Aoc2023s23.class.getResourceAsStream("res/t23.txt"))) {
 List<String> rows = new ArrayList<>(); 
 while (in.hasNext()) {
 String row = in.nextLine();
 rows.add(row);
 } 
 World world = new World(rows);
 Path path = new Path(world);
 path.move(1, 0);
 world.explore(path);
 System.out.println("max=" + world.maxPath);
 }
 }
}