Skip to content
TheChatArchiveThe Chat Archive
gpt-4-0314· openaiHugging Face Suzhen/CodeChat

Content 有一個 m*n 的方格棋盤,每個格子可能是 0 或 1,其中 0 代表可以通過而 1 代表不能通過。…

  1. User

    Content 有一個 m*n 的方格棋盤,每個格子可能是 0 或 1,其中 0 代表可以通過而 1 代表不能通過。

    現在有一個機器人從左上角編號(1,1)的格子出發,要到達右下角編號(m,n)的格子,每次可以往上下左右四個方向移動,我們要找到轉彎次數最少的路線。

    Input 第一行是兩個正整數 m 與 n,代表格子棋盤的列數與行數,

    接下來有 m 行,每行是一個長度為 n 僅由 0 與 1 組成的字串,代表方格棋盤由上往下由左至右的內容,出發與目的格子必然是 0。

    m 與 n 不超過 500。

    Output 最少的轉彎數。如果無法到達,則輸出-1。 用c++寫

  2. Assistant

    以下是一個使用 BFS (Breadth First Search) 的 C++ 程式碼解答:

    #include <iostream>
    #include <queue>
    #include <vector>
    
    using namespace std;
    
    #define MAX 505
    #define pii pair<int, int>
    #define piii pair<pii, int>
    #define mp make_pair
    
    int m, n; // 方格棋盤的大小
    char grid[MAX][MAX]; // 方格棋盤
    bool visited[MAX][MAX][5]; // 記錄訪問過的格子加上方向
    pii dir[] = {mp(1, 0), mp(-1, 0), mp(0, 1), mp(0, -1)}; // 上下左右四個方向的座標變化
    
    bool isValid(int x, int y, int d) {
        if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '0' && !visited[x][y][d])
            return true;
        return false;
    }
    
    int bfs() {
        queue<piii> q;
        q.push(mp(mp(0, 0), 0)); // 將起點放入Queue
    
        while (!q.empty()) {
            piii cur = q.front();
            q.pop();
    
            int x = cur.first.first;
            int y = cur.first.second;
            int d = cur.second;
    
            if(x == m-1 && y == n-1)
                return d;
    
            for (int i = 0; i < 4; i++) {
                int newX = x + dir[i].first;
                int newY = y + dir[i].second;
    
                if (isValid(newX, newY, i)) {
                    q.push(mp(mp(newX, newY), d + (i != cur.second)));
                    visited[newX][newY][i] = true;
                }
            }
        }
    
        return -1;
    }
    
    int main() {
        cin >> m >> n;
    
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                cin >> grid[i][j];
            }
        }
    
        cout << bfs() << endl;
    
        return 0;
    }
    

    這個程式碼首先將起點放入Queue中,然後進行 BFS 搜索。在搜索過程中,我們用一個 visited 陣列來記錄訪問過的格子和方向。當我們走到目標格子時返回最少的轉彎次數,如果遍歷完所有可能的格子都找不到目標點,那麼返回-1。