Sebelum Dijkstra bisa berjalan, kita perlu mengubah grid 2D menjadi graph berbobot. Pada bagian ini kita mendefinisikan struktur Grid, lokasi Cell, dan fungsi neighbors() yang mengembalikan sel-sel tetangga yang dapat dilalui dari suatu sel. Edge memiliki bobot seragam 1 — modifikasi ke bobot variabel (terrain cost) mudah dilakukan dengan menambah atribut biaya per sel.

Struktur Grid #

Grid direpresentasikan sebagai std::vector<std::string> di mana setiap string adalah satu baris. Konvensi karakter:

  • . — sel kosong, dapat dilalui, bobot 1.
  • # — rintangan, tidak dapat dilalui.
  • S — titik start, dapat dilalui (diperlakukan seperti .).
  • G — titik goal, dapat dilalui.
cpp 
struct Cell {
    int row, col;
    bool operator==(const Cell& o) const { return row == o.row && col == o.col; }
};

struct Grid {
    std::vector<std::string> cells;
    int rows, cols;

    Grid(std::vector<std::string> g) : cells(std::move(g)) {
        rows = (int)cells.size();
        cols = rows > 0 ? (int)cells[0].size() : 0;
    }

    bool inBounds(int r, int c) const {
        return r >= 0 && r < rows && c >= 0 && c < cols;
    }

    bool walkable(int r, int c) const {
        if (!inBounds(r, c)) return false;
        char ch = cells[r][c];
        return ch != '#';
    }
};

Fungsi neighbors #

Untuk sel tertentu, tetangga yang valid adalah empat sel di atas, bawah, kiri, kanan yang walkable(). Fungsi ini mengembalikan std::vector<Cell>:

cpp 
std::vector<Cell> neighbors(const Grid& g, const Cell& c) {
    static const int dr[] = {-1, 1, 0, 0};
    static const int dc[] = {0, 0, -1, 1};
    std::vector<Cell> result;
    for (int i = 0; i < 4; ++i) {
        int nr = c.row + dr[i];
        int nc = c.col + dc[i];
        if (g.walkable(nr, nc)) result.push_back({nr, nc});
    }
    return result;
}

Program Verifikasi #

Berikut program yang membangun grid contoh dan mencetak tetangga setiap sel yang dapat dilalui.

cpp 
#include <iostream>
#include <vector>

struct Cell {
    int row, col;
    bool operator==(const Cell& o) const { return row == o.row && col == o.col; }
};

struct Grid {
    std::vector<std::string> cells;
    int rows, cols;

    Grid(std::vector<std::string> g) : cells(std::move(g)) {
        rows = (int)cells.size();
        cols = rows > 0 ? (int)cells[0].size() : 0;
    }

    bool inBounds(int r, int c) const {
        return r >= 0 && r < rows && c >= 0 && c < cols;
    }

    bool walkable(int r, int c) const {
        if (!inBounds(r, c)) return false;
        char ch = cells[r][c];
        return ch != '#';
    }
};

std::vector<Cell> neighbors(const Grid& g, const Cell& c) {
    static const int dr[] = {-1, 1, 0, 0};
    static const int dc[] = {0, 0, -1, 1};
    std::vector<Cell> result;
    for (int i = 0; i < 4; ++i) {
        int nr = c.row + dr[i];
        int nc = c.col + dc[i];
        if (g.walkable(nr, nc)) result.push_back({nr, nc});
    }
    return result;
}

void printGrid(const Grid& g) {
    std::cout << "Grid " << g.rows << "x" << g.cols << ":\n";
    for (const auto& row : g.cells) std::cout << "  " << row << "\n";
    std::cout << "\n";
}

int main() {
    Grid g({
        ".....",
        ".###.",
        ".S.#.",
        "...#.",
        "...G."
    });
    printGrid(g);

    Cell sample = {2, 1};   // sel 'S'
    std::cout << "Tetangga sel (2,1):\n";
    for (const auto& nb : neighbors(g, sample)) {
        std::cout << "  -> (" << nb.row << "," << nb.col << ") = '"
                  << g.cells[nb.row][nb.col] << "'\n";
    }
    return 0;
}

Output yang Dihasilkan:

text 
Grid 5x5:
  .....
  .###.
  .S.#.
  ...#.
  ...G.

Tetangga sel (2,1):
  -> (3,1) = '.'
  -> (2,0) = '.'
  -> (2,2) = '.'

Tiga tetangga: sel (1,1) adalah # (rintangan) sehingga walkable() mengembalikan false dan sel tersebut tidak dimasukkan. Tetangga lain yang valid adalah (3,1), (2,0), dan (2,2) — semuanya dapat dilalui.

Bedah Baris Penting #

  1. struct Cell dengan operator==: diperlukan untuk membandingkan apakah dua sel sama — digunakan saat mendeteksi start dan goal, serta saat berhenti jika start = goal.
  2. Grid(std::vector<std::string> g): konstruktor mengambil ownership vector lewat std::move. Setelah konstruksi, pemanggil tidak bisa lagi mengakses vector asli — kepindahan eksplisit menghindari salinan tidak perlu.
  3. static const int dr[] = {-1, 1, 0, 0}: arah gerak baris untuk empat tetangga. static di dalam fungsi diinisialisasi sekali; const menjamin tidak diubah. Urutan atas-bawah-kiri-kanan dipilih agar konsisten dengan konvensi grafik.
  4. g.walkable(nr, nc): encapsulasi pengecekan. Tanpa fungsi ini, kode Dijkstra harus mengecek inBounds dan karakter # di setiap tempat — error-prone.
  5. result.push_back({nr, nc}): aggregate initialization membuat Cell tanpa konstruktor eksplisit. Sintaks ringkas dan jelas.

Ringkasan Bagian 1 #

Kita telah mendefinisikan struktur Grid dan Cell, fungsi neighbors() yang mengembalikan empat tetangga valid, dan konvensi karakter ./#/S/G. Pada Bagian 2, struktur ini menjadi masukan untuk algoritma Dijkstra.