gpt-4-0314· openai
Suzhen/CodeChat
Content 有一個 m*n 的方格棋盤,每個格子可能是 0 或 1,其中 0 代表可以通過而 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++寫
- 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。