ALGORITMA BFS

 Seorang penjelajah harus menemukan jalan dari S G di sebuah peta penuh dinding dan menuju jalan berbiaya. Dengan bantuan algoritma BFS yang memeriksa semua kemungkinan jalur secara teratur, penjelajahan berhasil menemukan rute paling murah. Setelah menghitung semua kemungkinan, biaya minimum untuk sampai ke tujuan adalah 7.

Code 

import java.util.*;

public class PetaBFS {

    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 n = 5, m = 5;

    static int[][] dist = new int[n][m];

    static int[] dx = {1, -1, 0, 0};

    static int[] dy = {0, 0, 1, -1};

    public static void main(String[] args) {

        for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);

        bfs(0, 0); // mulai dari S

        System.out.println("Biaya minimum: " + dist[4][4]);

    }

    static void bfs(int sx, int sy) {

        Queue<int[]> q = new LinkedList<>();

        dist[sx][sy] = 0;

        q.add(new int[]{sx, sy});

        while (!q.isEmpty()) {

            int[] cur = q.poll();

            int x = cur[0], y = cur[1];

            for (int k = 0; k < 4; k++) {

                int nx = x + dx[k], ny = y + dy[k];

                if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;

                if (peta[nx][ny] == '9') continue; // tembok

                int tambah = (peta[nx][ny] == 'S' || peta[nx][ny] == 'G') ? 0 : (peta[nx][ny] - '0');

                int newCost = dist[x][y] + tambah;

                if (newCost < dist[nx][ny]) {

                    dist[nx][ny] = newCost;

                    q.add(new int[]{nx, ny});

                }

            }

        }

    }

}

Output