Chương trình C++ tìm số bước đi lớn nhất giữa 2 ô trống trong lưới

Mô tả bài toán

Lưới h×w có ô chặn '#' và ô trống '.'. Chỉ đi ngang/dọc giữa các ô trống. Tìm khoảng cách lớn nhất (số bước) giữa 2 ô trống bất kỳ (đường đi ngắn nhất giữa chúng).

Ví dụ

h=4,w=4, grid={"..#.", "#.#.", "..##", "###."}. Đầu ra: 4 (từ (0,0) đến (2,0)).

Thuật toán (BFS từ mỗi ô trống)

1. Với mỗi ô trống (i,j), chạy BFS tính khoảng cách đến mọi ô trống khác.
2. Cập nhật res = max(res, dist[x][y]) trong BFS.
3. Độ phức tạp O((hw)^2), chấp nhận được với h,w ≤ 20.

Đoạn mã C++

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

int solve(int h,int w,vector<string> grid){
    int dx[4]={1,0,-1,0}, dy[4]={0,1,0,-1};
    vector<vector<int>> dist(h,vector<int>(w,-1));
    vector<vector<int>> reset(h,vector<int>(w,-1));
    int res=0;
    for(int i=0;i=0&&nx=0&&ny