python/C++专题课程/深度优先搜索/深度优先搜索-带完整路径.cpp

#include <bits/stdc++.h>

using namespace std;

/**
 * <EFBFBD><EFBFBD><EFBFBD>ܣ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>һ<EFBFBD><EFBFBD><EFBFBD>ṹ<EFBFBD>壬<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ƶ<EFBFBD><EFBFBD>ĺ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
 * <EFBFBD><EFBFBD><EFBFBD>ߣ<EFBFBD><EFBFBD>ƺ<EFBFBD>
 * ʱ<EFBFBD>䣺2019-11-17
 */
struct Node {
    int x, y;

    Node(int a, int b) {
        x = a;
        y = b;
    }
};

//<2F><>ͼ<EFBFBD><CDBC>С<EFBFBD><D0A1>һ<EFBFBD><D2BB><EFBFBD><EFBFBD><EFBFBD><EFBFBD>һ<EFBFBD>㷽<EFBFBD><E3B7BD><EFBFBD>洢
#define SIZE 100

//<2F><>
const int d[4][2] = {
        {-1, 0},  
        {0,  -1}, 
        {1,  0},  
        {0,  1}}; 

//<2F><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ĵ<EFBFBD>ͼ<EFBFBD><CDBC>Flase<73><65><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ߣ<EFBFBD>True:<3A><><EFBFBD><EFBFBD><EFBFBD>ߡ<EFBFBD>
bool _map[SIZE][SIZE];

//<2F><><EFBFBD>ǵ<EFBFBD>Ҫͼ<D2AA>λ<EFBFBD><CEBB><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ȴ<EFBFBD>һ<EFBFBD><D2BB>ԭͼ<D4AD><CDBC>
char pic[SIZE][SIZE];

//<2F>Dz<EFBFBD><C7B2>Ƿ<EFBFBD><C7B7>ʹ<EFBFBD>?
bool visit[SIZE][SIZE];

//<2F><><EFBFBD><EFBFBD><EFBFBD>ߵ<EFBFBD>·<EFBFBD><C2B7>
vector<Node> path;

//ȫ<><C8AB>·<EFBFBD><C2B7><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>¼<EFBFBD><C2BC><EFBFBD><EFBFBD>
vector<vector<Node> > allpath;

//<2F><>ͼ  m:<3A>У<EFBFBD>n:<3A><>
int m, n;

//S:<3A><><EFBFBD><EFBFBD><EFBFBD><EFBFBD>,T:<3A>յ<EFBFBD> <20><><EFBFBD><EFBFBD>ôsx,sy<73><79><EFBFBD>dz<EFBFBD><C7B3><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>꣬tx,ty<74><79><EFBFBD><EFBFBD><EFBFBD>յ<EFBFBD><D5B5><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
int sx, sy, tx, ty;

//<2F><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
void dfs(int x, int y) {
    //<2F><><EFBFBD><EFBFBD><EFBFBD>ҵ<EFBFBD><D2B5><EFBFBD><EFBFBD>յ<EFBFBD>T<EFBFBD><54><EFBFBD><EFBFBD>ôx=tx,y=ty
    if (x == tx && y == ty) {
        //<2F><>¼<EFBFBD><C2BC><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
        path.push_back(Node(x, y));

        //<2F><>·<EFBFBD><C2B7><EFBFBD><EFBFBD>¼<EFBFBD><C2BC><EFBFBD><EFBFBD>
        allpath.push_back(path);

        //<2F>˳<EFBFBD>׼<EFBFBD><D7BC><EFBFBD><EFBFBD>һ<EFBFBD>γ<EFBFBD><CEB3><EFBFBD>,<2C><><EFBFBD>ε<EFBFBD><CEB5><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ҵ<EFBFBD><D2B5><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ˣ<EFBFBD><CBA3><EFBFBD><EFBFBD><EFBFBD>Ҫ<EFBFBD><D2AA><EFBFBD><EFBFBD><EFBFBD>еĿ<D0B5><C4BF>ܶ<EFBFBD><DCB6>ҵ<EFBFBD><D2B5><EFBFBD>Ȼ<EFBFBD><C8BB><EFBFBD>Ա<EFBFBD><D4B1>ҵ<EFBFBD><D2B5><EFBFBD>С<EFBFBD><D0A1>·<EFBFBD><C2B7><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ԣ<EFBFBD><D4A3><EFBFBD>Ҫ<EFBFBD><D2AA>ͣ<EFBFBD>Ļ<EFBFBD><C4BB>ˣ<EFBFBD>
        path.pop_back();
        return;
    }
    if (!_map[x][y]) return; //<2F><><EFBFBD><EFBFBD><EFBFBD>߾Ͳ<DFBE><CDB2><EFBFBD>
    if (visit[x][y]) return; //<2F>߹<EFBFBD><DFB9><EFBFBD>Ҳ<EFBFBD><D2B2><EFBFBD><EFBFBD>

    //<2F><>¼<EFBFBD>߹<EFBFBD><DFB9><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>(·<><C2B7>)
    path.push_back(Node(x, y));
    //<2F><>ʶ<EFBFBD><CAB6><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
        dfs(xx, yy);
    }
    visit[x][y] = 1;
    //<2F>ĸ<EFBFBD><C4B8><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>г<EFBFBD><D0B3><EFBFBD>
    for (int i = 0; i < 4; ++i) {
        int xx = x + d[i][0], yy = y + d[i][1];
        //<2F>ĸ<EFBFBD><C4B8><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>̽<EFBFBD><CCBD>
    //<2F><>ֽ<EFBFBD><D6BD><EFBFBD><EFBFBD>ȡ<EFBFBD>أ<EFBFBD><D8A3><EFBFBD>δû<CEB4><C3BB><EFBFBD>߹<EFBFBD>
    visit[x][y] = 0;
    path.pop_back();

    return;
}

/**
 * <EFBFBD><EFBFBD><EFBFBD>ܣ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>·<EFBFBD><EFBFBD>
 * <EFBFBD><EFBFBD><EFBFBD>ߣ<EFBFBD><EFBFBD>ƺ<EFBFBD>
 * ʱ<EFBFBD>䣺2019-11-17
 * @param x
 */
void showpath(vector<Node> x) {
    char s[SIZE][SIZE];
    for (int i = 0; i < n; ++i) {
        strcpy(s[i], pic[i]);
    }
    for (int i = 0; i < x.size(); ++i) {
        s[x[i].x - 1][x[i].y - 1] = '+';
    }
    for (int i = 0; i < m; ++i) puts(s[i]);
    printf("step = %d\n", x.size() - 1);
    printf("\n");
}

//<2F>Ա<EFBFBD><D4B1><EFBFBD><EFBFBD>ַ<EFBFBD><D6B7><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ȼ<EFBFBD><C8BC>ߣ<EFBFBD><DFA3><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>٣<EFBFBD><D9A3><EFBFBD><EFBFBD><EFBFBD><EFBFBD>١<EFBFBD>
bool cmp(vector<Node> x, vector<Node> y) {
    return x.size() < y.size();
}

int main() {

    //<2F><>ȡm:<3A>У<EFBFBD>n:<3A><>
    scanf("%d %d", &m, &n);

    //<2F><>ν<EFBFBD><CEBD>ʼֵ<CABC><D6B5><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ζ<EFBFBD><CEB6><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ĵ<EFBFBD><C4B4><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ҫ<EFBFBD>ڵ<EFBFBD>ͼ<EFBFBD><CDBC><EFBFBD>ҵ<EFBFBD>S<EFBFBD><53>T<EFBFBD><54>Ȼ<EFBFBD><C8BB><EFBFBD>޸<EFBFBD>sx,sy,tx,ty<74>ĸ<EFBFBD>ֵ<EFBFBD><D6B5>
    //<2F>Թ<EFBFBD><D4B9><EFBFBD><EFBFBD>ڣ<EFBFBD>
    sx = 1; //<2F><>ʼֵ
    sy = 1; //<2F><>ʼֵ

    //<2F>Թ<EFBFBD><D4B9><EFBFBD><EFBFBD>ڣ<EFBFBD>
    tx = m; //<2F><>ʼֵ
    ty = n; //<2F><>ʼֵ

    //<2F><><EFBFBD>ж<EFBFBD>ȡ<EFBFBD><C8A1><EFBFBD>ݣ<EFBFBD><DDA3><EFBFBD>m<EFBFBD><6D>
    for (int i = 0; i < m; i++) {
        scanf("%s", pic[i]); //<2F><><EFBFBD>ж<EFBFBD><D0B6><EFBFBD><EFBFBD><EFBFBD>ͼ
        char s[SIZE];
        strcpy(s, pic[i]);//<2F><><EFBFBD><EFBFBD><EFBFBD>е<EFBFBD>ͼ<EFBFBD><CDBC><EFBFBD>ݵ<EFBFBD>s<EFBFBD><73>

        //<2F><><EFBFBD>б<EFBFBD><D0B1><EFBFBD>
        for (int j = 0; j < n; j++) {
            //ȡ<><C8A1><EFBFBD><EFBFBD>ǰֵ
            char c = s[j];

            //<2F><>ʼ<EFBFBD><CABC>
            if (c == 'S') {
                sx = i + 1;
                sy = j + 1;
                _map[i + 1][j + 1] = true;
            }//<2F>յ<EFBFBD>
            else if (c == 'T') {
                tx = i + 1;
                ty = j + 1;
                _map[i + 1][j + 1] = true;
            }//<2F><><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
            else if (c == '#') {
                _map[i + 1][j + 1] = false;
            } else//<2F><><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
            {
                _map[i + 1][j + 1] = true;
            };
        }
    }

    //<2F><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ȣ<EFBFBD><C8A3><EFBFBD><EFBFBD><EFBFBD><EFBFBD>㷨
    dfs(sx, sy);

    //<2F><><EFBFBD><EFBFBD>û<EFBFBD><C3BB><EFBFBD>ҵ<EFBFBD><D2B5><EFBFBD><EFBFBD><EFBFBD>
    if (allpath.size() == 0) {
        printf("û<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>õķ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>\n");
    } else {
        //<2F><><EFBFBD><EFBFBD><EFBFBD>ݽ<EFBFBD><DDBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ҳ<EFBFBD><D2B3><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ٵķ<D9B5><C4B7><EFBFBD>
        sort(allpath.begin(), allpath.end(), cmp);

        //<2F><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ѷ<EFBFBD><D1B7><EFBFBD>
        printf("<EFBFBD><EFBFBD><EFBFBD>ѷ<EFBFBD><EFBFBD><EFBFBD>:\n");
        showpath(allpath[0]);

        //<2F><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>෽<EFBFBD><E0B7BD>
        printf("<EFBFBD><EFBFBD><EFBFBD>෽<EFBFBD><EFBFBD>:\n");
        for (int i = 1; i < allpath.size(); ++i) {
            showpath(allpath[i]);
        }
        //<2F><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
        printf("<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD> = %d\n", allpath.size());
    }
    return 0;
}
/*
 https://blog.csdn.net/szdytom/article/details/87537876

-- <EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Dz<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
5 6
....S#
.##...
.#..#.
#..##.
.T....


<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
4 4
S.##
..##
#..#
##.T


5 6
....S#
.##...
.#..#.
#..##.
.T....

*/