โปรแกรม C++ หาจำนวนการเคลื่อนที่สูงสุดระหว่างเซลล์ว่างในกริด

กริด h×w มีเซลล์บล็อก (#) และว่าง (.) ต้องการหาจำนวนการเคลื่อนที่ (ขั้นตอน) สูงสุดที่ต้องใช้ เพื่อเดินจากเซลล์ว่างหนึ่งไปอีกเซลล์ว่างหนึ่ง (เดิน 4 ทิศทาง ไม่ทะลุบล็อก) คือเส้นทางสั้นที่สุดที่ยาวที่สุด (diameter) ของกราฟเซลล์ว่าง

ตัวอย่าง: h=4,w=4, grid={"..#.", "#.#.", "..##", "###."} ผลลัพธ์: 4 (จาก (0,0) ถึง (2,0) ใช้ 4 ขั้น)

ขั้นตอนการแก้ปัญหา (BFS จากทุกเซลล์ว่าง)

1. ทิศทาง 4 ด้าน: xdir={1,0,-1,0}, ydir={0,1,0,-1}
2. สำหรับทุกเซลล์ (i,j) ที่เป็น .:
   • รีเซ็ต dist = -1 ทั้งกริด, dist[i][j]=0, BFS
   • ระหว่าง BFS อัปเดต res = max(res, dist[x][y])
3. คืนค่า res

หมายเหตุ: วิธีนี้ O((hw)²) ใช้ได้กับกริดเล็ก

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

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

int solve(int h, int w, vector<string> grid) {
    int xdir[4] = {1, 0, -1, 0};
    int ydir[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 < h; i++) {
        for (int j = 0; j < w; j++) {
            dist = reset;
            if (grid[i][j] == '.') {
                dist[i][j] = 0;
                queue<pair<int,int>> q;
                q.push({i, j});
                while (!q.empty()) {
                    int x = q.front().first;
                    int y = q.front().second;
                    res = max(dist[x][y], res);
                    q.pop();
                    for (int k = 0; k < 4; k++) {
                        int px = x + xdir[k], py = y + ydir[k];
                        if (px >= 0 && px < h && py >= 0 && py < w) {
                            if (grid[px][py] == '.' && dist[px][py] == -1) {
                                dist[px][py] = dist[x][y] + 1;
                                q.push({px, py});
                            }
                        }
                    }
                }
            }
        }
    }
    return res;
}

int main() {
    int h = 4, w = 4;
    vector<string> grid = {"..#.", "#.#.", "..##", "###."};
    cout << solve(h, w, grid);
    return 0;
}

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

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

Output: 4