Promble Description

定義一個(gè)二維數(shù)組：

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,};

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

INPUT

一個(gè)5 × 5的二維數(shù)組，表示一個(gè)迷宮。數(shù)據(jù)保證有唯一解。

OUTPUT

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

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

問(wèn)題鏈接：http://poj.org/problem?id=3984

問(wèn)題分析：根據(jù)DFS算法的思想，再建立一個(gè)數(shù)組儲(chǔ)存最少步數(shù)所走的路徑，注意格式，逗號(hào)后面有個(gè)空格

AC代碼

#include<iostream> using namespace std; int m[10][10],lx[100],ly[100],min1=9999999,vis[30][30],xe[100],ye[100]; //m記錄地圖，ly,lx記錄路徑； int n[4][2] = { {1,0},{0,1},{-1,0},{0,-1} }；//4個(gè)方向 void DFS(int x, int y, int step)//x,y為當(dāng)前位置，step為走到該位置花的步數(shù) {if (x == 4 && y == 4)//判斷是否到達(dá)終點(diǎn){if (step < min1){min1 = step;//記錄最小步數(shù)for (int i = 0; i < step; i++){xe[i] = lx[i];//記錄所走的路徑y(tǒng)e[i] = ly[i];}}return;}for (int i = 0; i < 4; i++)//從4個(gè)方向探索{int tx = x + n[i][0];int ty = y + n[i][1];if (tx < 0 || ty < 0 || tx>4 || ty>4)continue;//判斷是否越界if (m[tx][ty] == 0 && vis[tx][ty] == 0)//判斷是否訪問(wèn)過(guò)，能不能走{lx[step] = tx;//記錄路徑ly[step] = ty;vis[tx][ty] = 1;//標(biāo)記訪問(wèn)DFS(tx, ty, step + 1);//探索下一步，步數(shù)加一vis[tx][ty] = 0;//回溯取消標(biāo)記}} } 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 < min1; i++){printf("(%d, %d)", xe[i], ye[i]);if (i < min1 - 1)printf("\n");} }

（轉(zhuǎn)發(fā)）DFS算法博客鏈接：https://www.cnblogs.com/OctoptusLian/p/7429645.html

總結(jié)

以上是生活随笔為你收集整理的POJ3904(dfs)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。