定義一個二維數組：

int maze[5][5] = {0, 1, 0, 0, 0,0, 1, 0, 1, 0,0, 0, 0, 0, 0,0, 1, 1, 1, 0,0, 0, 0, 1, 0,};

它表示一個迷宮，其中的1表示墻壁，0表示可以走的路，只能橫著走或豎著走，不能斜著走，要求編程序找出從左上角到右下角的最短路線。

Input

一個5 × 5的二維數組，表示一個迷宮。數據保證有唯一解。

Output

左上角到右下角的最短路徑，格式如樣例所示。

Sample Input

0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0

Sample Output

(0, 0) (1, 0) (2, 0) (2, 1) (2, 2) (2, 3) (2, 4) (3, 4) (4, 4)

問題分析：簡單的DFS，多加一步記錄其走過的路徑

AC代碼：

#include<iostream> #include<cstring> #include<stdio.h> using namespace std; int m[30][30],vis[30][30],mi=99999999,xs[30],ys[30],xe[30],ye[30],tx,ty; int n[4][2] = { 1,0,0,1,-1,0,0,-1 }; void dfs(int x, int y, int step) {if (x == 4 && y == 4){if (mi > step)mi = step;for (int i = 0; i < step; i++){xe[i] = xs[i];ye[i] = ys[i];}return;}for (int i = 0; i < 4; i++){tx = x + n[i][0];ty = y + n[i][1];if (tx > 4 || ty > 4 || tx < 0 || ty < 0)continue;if (vis[tx][ty] != 1&&m[tx][ty]!=1){vis[tx][ty] = 1;xs[step] = tx;ys[step] = ty;dfs(tx, ty, step + 1);vis[tx][ty] = 0;}}} int main() {for (int i = 0; i < 5; i++)for (int j = 0; j < 5; j++)cin >> m[i][j];dfs(0, 0, 0);printf("(0, 0)\n");for (int i = 0; i < mi; i++)printf("(%d, %d)\n", xe[i], ye[i]); }

?

總結

以上是生活随笔為你收集整理的康复题11的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。