在图中寻找最短路径-----深度优先算法C++实现

求从图中的任意一点（起点）到另一点（终点）的最短路径，最短距离；

图中有数字的点表示为图中的不同海拔的高地，不能通过；没有数字的点表示海拔为0，为平地可以通过；

这个是典型的求图中两点的最短路径；本例，用深度优先算法来实现；

在每一个点都有四个方向（有的点的有些方向不能通过），所以在每一个点处要处理四种方向的情况；

深度优先算法函数怎么写？

也就是写递归函数。。。但是递归函数肿么写？？？

第一：判断初始态，从起点出发，刚开始步数为0；dfs(start_x, start_y, 0);

第二：从起点出发，要做什么事情？尝试四个方向的走法。

在每个方向上要什么？先判断这个点是否到达边界，再判断这个点是否走过并且是否是高地；如果不是高地也没有走过，则再从该点出发，做和之前的点一样的事情；

dfs(tx, ty, step+1);

第二：判断终止条件，到达终点，判断当前步数；返回；

/*************************************************************************

	> File Name: search_min_step.cpp

	> Author:

	> Mail:

	> Created Time: 2015年11月13日 星期五 21时49分41秒

 ************************************************************************/

#include<iostream>

using namespace std;

const int MAX_X = 50;

const int MAX_Y = 50;

int min_step = 10000;

int my_x, my_y;

int map[MAX_X][MAX_Y];

int book[MAX_X][MAX_Y];

int start_x, start_y;

int dest_x, dest_y;

void dfs(int x, int y, int step)

{

    /*up, right, down, left*/

    int next[4][2] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};

    int tx, ty;

    if (x == dest_x && y == dest_y){

        if (step < min_step)

            min_step = step;

        return;

    }

    for (int i = 0; i < 4; i++){

        tx = x + next[i][0];

        ty = y + next[i][1];

        if (tx > my_x || ty > my_y || tx < 0 || ty < 0)

            continue;

        if (map[tx][ty] == 0 && book[tx][ty] == 0){

            book[tx][ty] = 1;

            dfs(tx, ty, step+1);

            book[tx][ty] = 0;

        }

    }

}

void input_map_info()

{

    cout << "input the max x:";

    cin >> my_x;

    cout << "input the max y:";

    cin >> my_y;

    cout << "input the map information:\n";

    for (int i = 1; i <= my_x; i++){

        for (int j = 1; j <= my_y; j++){

            cin >> map[i][j];

        }

    }

}

int main()

{

    input_map_info();

    cout << "input the source location:";

    cin >> start_x >> start_y;

    cout << "input the destat location:";

    cin >> dest_x >> dest_y;

    book[start_x][start_y] = 1;

    dfs(start_x, start_y, 0);

    cout << "min_step = " << min_step << endl;

    return 0;

}