描述

当你站在一个迷宫里的时候，往往会被错综复杂的道路弄得失去方向感，如果你能得到迷宫地图，事情就会变得非常简单。
假设你已经得到了一个n*m的迷宫的图纸，请你找出从起点到出口的最短路。

输入

第一行是两个整数n和m(1 <= n,m <= 100)，表示迷宫的行数和列数。
接下来n行，每行一个长为m的字符串，表示整个迷宫的布局。字符’.’表示空地，’#’表示墙，’S’表示起点,’T’表示出口。

输出

输出从起点到出口最少需要走的步数。(你不能起出迷宫外)

样例输入
3 3
S#T
.#.
...

样例输出
6

解题思路：

1、先找到入口和出口的位置，通过二维数组记录其位置
2、从入口开始，对上下左右进行判断找点，然后通过另一个数组来记录走过的路径
3、走过的位置可以标记，但这里可以用次序来标记，也就是顺带能实现走了几步
4、因为每一次的判断都相同，所以可以使用“递归”
5、如果能够使用递归，那么同样也就能通过for循环来解决。### 出错点：
1、没有使用自增，或者加1后赋值回去，导致计数根本没有改变
2、不知道二维数组的初始化要用memset，并且不够理解memet是如何赋值给整型数组的

代码原封不动地记录了我思考的整个过程^_^

​ 
#include <iostream>
#include <cstring>
using namespace std;
char map[101][101];//字符数组
int done[101][101];//二维数组不能简单地像一维数组直接={ 0 }
int n, m;// n行m列
int minstep = 0;//记录最小步数

                //从入口进入后开始判断
void path(int in1, int in2, int out1, int out2) {
    int count = done[in1][in2];
    //整个函数的思想是：每一次都是一个新的起点开始，对上下左右进行判断
    //所以，就可以使用递归的方法，并且当新的起点恰好就是出口的时候，迷宫结束。
    if (in1 == out1 && in2 == out2) {
        minstep = count;
    }
    count++;//可以把count先自增

    //下面开始对上下左右进行判断
    //在“最外层”是需要分别考虑的，所以有限制条件
    //判断“上”
    if (in1 > 0 && map[in1 - 1][in2] != '#' && done[in1 - 1][in2] > count) {
        done[in1 - 1][in2] = count;//把这个位置记录成下一步要走的次序
                                       //然后再以这个点作为新的起点，再次判断
        path(in1 - 1, in2, out1, out2);
    }
    //后面的三个方向都如此判断
    //判断“下”
    if (in1 < n - 1 && map[in1 + 1][in2] != '#' && done[in1 + 1][in2] > count) {
        
        done[in1 + 1][in2] = count;
        path(in1 + 1, in2, out1, out2);
    }
    //判断“左”
    if (in2 > 0 && map[in1][in2 - 1] != '#'&& done[in1][in2 - 1] > count) {
        done[in1][in2 - 1] = count;
        path(in1, in2 - 1, out1, out2);
    }
    //判断“右”
    if (in2 < m - 1 && map[in1][in2 + 1] != '#' && done[in1][in2 + 1] > count) {
        done[in1][in2 + 1] = count;
        path(in1, in2 + 1, out1, out2);
    }


}

int main() {
    int inx, iny, outx, outy;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            //在记录地图的同时，对入口和出口进行判断
            cin >> map[i][j];
            if (map[i][j] == 'S') {
                inx = i;
                iny = j;
            }
            if (map[i][j] == 'T') {
                outx = i;
                outy = j;
            }
        }
    }
    
    memset(done, 2, sizeof(done));//赋的值是0x02020202
    
    /*
    //使用循环进行赋值
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            done[i][j] = 99;
        }
    }
    cout << endl;
    //验证memset到底赋了什么值
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << done[i][j];
        }
    }
    cout << endl;
    */
    

    done[inx][iny] = 0;//起点设置为第0步
    path(inx, iny, outx, outy);
    cout << minstep << endl;

    return 0;
}

 思考的过程比最后的结果要重要^_^