โปรแกรม C++ หาจำนวนครั้งที่หุ่นยนต์ต้องกระโดดในกริด

กริด h×w มีอุปสรรค # และทาง . หุ่นยนต์อยู่ที่ c(x,y) ต้องไป d(p,q) การเคลื่อนที่:

• เดินปกติ: ไป 4 ทิศทางติดกัน (cost 0 jump)
• กระโดด: ไปจุดใดก็ได้ในพื้นที่ 5×5 รอบตัว (cost 1 jump)
• ไม่ boleh ออกนอกกริด หรือลงอุปสรรค

หาจำนวนกระโดดน้อยที่สุด (0-1 BFS)

ตัวอย่าง: h=4,w=4, c={2,1}, d={4,4}, grid={"#...",".##.","...#","..#."} ผลลัพธ์: 1

ขั้นตอนการแก้ปัญหา (0-1 BFS / Deque)

1. สร้าง grid จาก initGrid
2. dst[i][j] = จำนวนกระโดดน้อยที่สุดถึง (i,j) เริ่มต้น INF
3. Deque เริ่มจาก s (ปรับดัชนี 0-based) dst[s]=0
4. Pop หน้า deque → nd ลูป diffx=-2..2, diffy=-2..2:
   • tm = |diffx|+|diffy| ถ้า tm>1 คือกระโดด (w=1) มิฉะนั้นเดิน (w=0)
   • ถ้าในกริดและเป็น . และ dst[nd]+w < dst[nx][ny] อัปเดต
   • w==0 → push_front, w==1 → push_back
5. คืน dst[t] (หรือ -1 ถ้า INF)

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;
#define N 100
int h, w;
pair<int,int> s, t;
string grid[N];
int dst[N][N];

struct node { int a, b, e; };

bool check(int a, int b) {
    return a >= 0 && a < h && b >= 0 && b < w;
}

void bfs(int a, int b) {
    for (int i = 0; i < h; i++)
        for (int j = 0; j < w; j++)
            dst[i][j] = INF;
    dst[a][b] = 0;
    deque<node> dq;
    dq.push_back({a, b, 0});
    while (!dq.empty()) {
        node nd = dq.front(); dq.pop_front();
        if (nd.e > dst[nd.a][nd.b]) continue;
        for (int dx = -2; dx <= 2; dx++) {
            for (int dy = -2; dy <= 2; dy++) {
                int tm = abs(dx) + abs(dy);
                int nx = nd.a + dx, ny = nd.b + dy;
                if (check(nx, ny) && grid[nx][ny] == '.') {
                    int w = (tm > 1) ? 1 : 0;
                    if (dst[nd.a][nd.b] + w < dst[nx][ny]) {
                        dst[nx][ny] = dst[nd.a][nd.b] + w;
                        if (w == 0) dq.push_front({nx, ny, dst[nx][ny]});
                        else dq.push_back({nx, ny, dst[nx][ny]});
                    }
                }
            }
        }
    }
}

void solve(pair<int,int> c, pair<int,int> d, string initGrid[]) {
    s = c; t = d;
    s.first--; s.second--; t.first--; t.second--;
    for (int i = 0; i < h; i++) grid[i] = initGrid[i];
    bfs(s.first, s.second);
    cout << (dst[t.first][t.second] == INF ? -1 : dst[t.first][t.second]) << '\n';
}

int main() {
    h = 4; w = 4;
    pair<int,int> c = {2,1}, d = {4,4};
    string initGrid[] = {"#...", ".##.", "...#", "..#."};
    solve(c, d, initGrid);
    return 0;
}

อินพุต / เอาต์พุต

Input: 4, 4, {2,1}, {4,4}, {"#...", ".##.", "...#", "..#."}

Output: 1