Brute Force

 import java.util.*;

public class brut {

    // Peta berisi S (start), G (goal), angka = biaya, dan 9 = tembok

    static char[][] peta = {

            {'S', '1', '1', '9', '1'},

            {'1', '2', '1', '1', '1'},

            {'1', '9', '2', '9', '1'},

            {'1', '1', '2', '1', '1'},

            {'1', '1', '1', '2', 'G'}

    };

    static int min = Integer.MAX_VALUE; // simpan biaya minimum

    static List<List<String>> semuaJalur = new ArrayList<>(); // simpan semua jalur dengan biaya minimum

    static List<String> jalurSekarang = new ArrayList<>();    // simpan jalur yang sedang dilalui

    public static void main(String[] args) {

        System.out.println("Biaya Minimum: " + biaya(peta));

        System.out.println("Jalur dengan biaya minimum:");

        // cetak semua jalur terbaik

        for (List<String> jalur : semuaJalur) {

            System.out.println(jalur);

        }

    }

    // cari posisi 'S' lalu mulai pencarian

    private static int biaya(char[][] arr) {

        int x = 0, y = 0;

        // cari koordinat 'S'

        for (int i = 0; i < 5; i++) {

            for (int j = 0; j < 5; j++) {

                if (arr[i][j] == 'S') {

                    x = i;

                    y = j;

                    break;

                }

            }

        }

        // mulai jalur dari 'S'

        jalan(x, y, 0);

        return min;

    }

    // rekursi untuk menjelajah semua kemungkinan jalur

    private static void jalan(int i, int j, int cost) {

        // kondisi keluar: di luar peta, tembok '9', atau sudah pernah dikunjungi 'x'

        if (i < 0 || i > 4 || j < 0 || j > 4 || peta[i][j] == '9' || peta[i][j] == 'x') return;

        // jika sampai tujuan 'G'

        if (peta[i][j] == 'G') {

            if (cost < min) {

                min = cost;               // update biaya minimum

                semuaJalur.clear();       // hapus jalur lama

                semuaJalur.add(new ArrayList<>(jalurSekarang)); // simpan jalur baru

            } else if (cost == min) {

                semuaJalur.add(new ArrayList<>(jalurSekarang)); // simpan jika sama dengan min

            }

            return;

        }

        // simpan nilai asli cell

        char temp = peta[i][j];

        // konversi char ke integer biaya (S = 0)

        int nilai = (temp == 'S') ? 0 : (temp - '0');

        // tandai sudah dilewati agar tidak balik lagi

        peta[i][j] = 'x';

        // simpan koordinat ke jalur saat ini

        jalurSekarang.add("(" + i + "," + j + ")");

        // jelajah ke 4 arah

        jalan(i - 1, j, cost + nilai); // atas

        jalan(i + 1, j, cost + nilai); // bawah

        jalan(i, j + 1, cost + nilai); // kanan

        jalan(i, j - 1, cost + nilai); // kiri

        // backtrack: hapus langkah terakhir & kembalikan nilai cell

        jalurSekarang.remove(jalurSekarang.size() - 1);

        peta[i][j] = temp;

    }

}