典型BFS。
#include <iostream> #include <memory.h> #include <queue> #include <map> #define LEN 5 using namespace std; int graph[LEN][LEN]; int ans = 0; int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1}; void printAns(map<int, int> &visit, int p) { if (p == -1) return; int prev = visit[p]; printAns(visit, prev); int x = p / 5; int y = p - x * 5; cout << "(" << x << ", " << y << ")" << endl; } int main() { memset(graph, 0, sizeof(graph)); int n = 5; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> graph[i][j]; } } queue<int> que; // (3,4) is 3*5+4 = 19 map<int, int> visit; // points to it's prev que.push(0); visit[0] = -1; int dest = 4 * 5 + 4; while (!que.empty()) { int point = que.front(); que.pop(); if (point == dest) break; int x = point / 5; int y = point - x * 5; for (int i = 0; i < 4; i++) { int next_x = x + dx[i]; int next_y = y + dy[i]; if (next_x >= 5 || next_x < 0 || next_y >=5 || next_y < 0) continue; if (graph[next_x][next_y] == 1) continue; int key = next_x * 5 + next_y; if (visit.count(key) != 0) continue; visit[key] = point; que.push(key); } } // print ans from dest printAns(visit, dest); return 0; }