python/C++专题课程/深度优先搜索/解救小哈之读取数据文件.cpp

#include <bits/stdc++.h>

using namespace std;

//最小步数
int _min = INT_MAX;

//行数
const int n = 5;
//列数
const int m = 4;

//小哈位置x坐标+y坐标
const int p = 2;
const int q = 3;

//地图
int a[n][m];

//标记数组，哪个走过了?
int book[n][m];


/**
 * 功能：深度优先搜索走迷宫
 * 作者：黄海
 * 时间：2019-11-17
 * @param x
 * @param y
 * @param step
 */
void dfs(int x, int y, int step) {
    int next[4][2] = {
            {0,  1},//向右走
            {1,  0},//向下走
            {0,  -1},//向左走
            {-1, 0},//向上走
    };
    int tx, ty, k;
    if (x == p && y == q)  //判断是否到达小哈的位置
    {
        if (step < _min)
            _min = step;  //更新最小值
        return;
    }
    /*枚举四种走法*/
    for (k = 0; k <= 3; k++) {
        /*计算下一个点的坐标*/
        tx = x + next[k][0];
        ty = y + next[k][1];
        if (tx < 0 || tx > n - 1 || ty < 0 || ty > m - 1)  //判断是否越界
            continue;
        /*判断该点是否为障碍物或者已经在路径中*/
        if (a[tx][ty] == 0 && book[tx][ty] == 0) {
            book[tx][ty] = 1;  //标记这个点已经走过
            dfs(tx, ty, step + 1);  //开始尝试下一个点
            book[tx][ty] = 0;  //尝试结束，取消这个点的标记
        }
    }
    return;
}

int main() {
    //起点和终点坐标
    int startx = 0;
    int starty = 0;

    //从文件中读取地图数据
    string file = "../data.in";
    //fstream 流方法读数据
    ifstream fin(file);

    //读取地图
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            fin >> a[i][j];

    //关闭文件
    fin.close();
    fin.clear(ios::goodbit);

    /*从起点开始搜索*/
    book[startx][starty] = 1;  //标记起点已经在路径中，防止后面重复走

    dfs(startx, starty, 0);  //第一个参数是起点的x坐标，以此类推是起点的y坐标，初始步数为0
    printf("%d", _min);  //输出最短步数
    return 0;
}