Chương trình C++ tìm số nhảy ít nhất của robot trong lưới 5x5

Mô tả bài toán

Lưới h×w, '#' chướng ngại, '.' đường. Robot từ ô đến ô . Di chuyển:

• Đi 1 ô lên/xuống/trái/phải (chi phí 0 nhảy).
• Nhảy đến bất kỳ ô nào trong khu vực 5×5 tâm tại ô hiện tại (chi phí 1 nhảy).
• Không đi vào '#' và không ra khỏi lưới.

Ví dụ

h=4,w=4, c={2,1}, d={4,4}, grid={"#...",".##.","...#","..#."}. Đầu ra: 1.

Thuật toán (0-1 BFS / Deque)

1. Trạng thái: ô (x,y), khoảng cách = số nhảy.
2. Deque: đi bộ (4 hướng) → push_front (chi phí 0); nhảy (25 ô trong 5×5) → push_back (chi phí 1).
3. 0-1 BFS đảm bảo tìm được đường đi số nhảy nhỏ nhất.

Đoạn mã C++

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

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

struct Node{int x,y,d;};

bool inside(int x,int y){
    return x>=0 && x=0 && ydist[nd.x][nd.y]) continue;
        for(int dx=-2;dx<=2;dx++) for(int dy=-2;dy<=2;dy++){
            int nx=nd.x+dx, ny=nd.y+dy;
            if(!inside(nx,ny) || grid[nx][ny]=='#') continue;
            int w=(abs(dx)+abs(dy)>1)?1:0;
            if(dist[nd.x][nd.y]+w < dist[nx][ny]){
                dist[nx][ny]=dist[nd.x][nd.y]+w;
                if(w==0) dq.push_front({nx,ny,dist[nx][ny]});
                else dq.push_back({nx,ny,dist[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