爬格子呀7-1

不想说话，图论的模型求解

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
int k, n, g[21][21];
vector<int>neigh[20];
vector<int>path;
int v[20];//v为标记数组
int len;
//通过dfs提前检查能否到达终点
//这个例子说明可以通过dfs在图中进行最短路的搜寻
bool dfs(int u) {
    if (u == k)
        return true;
    else {
        //便历u的每个邻居i，通过递归遍历
        for (int i = 0; i < neigh[u].size(); i++) {
            //这里其实可以直接dfs（neigh[u][i]),但是会造成相同点的多次重复遍历
            if (!v[neigh[u][i]]) {//如果neigh[u][i]没有被标记（遍历）过，就对其进行递归遍历
                int x = neigh[u][i];
                v[x] = 1;
                if (dfs(x))
                    //这里只需要判断能不能找到，故不用进行标记数组的重新置零
                    return true;
            }
        }
    }
}

void find_path() {
    len++;
    for (int i = 0; i < path.size(); i++) {
        printf("%d%c", path[i], i == path.size() ? "/n" : " ");
    }
}

void search(int u) {
    if (u == k)
    {
        find_path();
        return;
    }
    else {
        for (int i = 0; i < neigh[u].size(); i++) {
            if (!v[neigh[u][i]]) {
                int x = neigh[u][i];
                v[x] = 1;
                path.push_back(neigh[u][i]);
                search(x);
                path.resize(path.size() - 1);
                v[x] = 0;
            }
        }
    }
}

int main() {
    int a, b;
    cin >> k >> a >> b;
    memset(g, 0, sizeof(g));
    n = k;
    while (a || b) {
        n = max(n, max(a, b));
        g[a][b] = g[b][a] = 1;//邻接矩阵的填充
    }
    //邻接表，通过一个二维的vector来获得与节点i相关联的节点编号
    //一共i个点
    for (int i = 1; i <= n; i++) {
        neigh[i].clear();
        for (int j = 1; j <= n; j++) {
            if (g[i][j])//以i为坐标原点，j为变量，进行i的邻居编号
                neigh[i].push_back(g[i][j]);
        }
    }
    memset(v, 0, sizeof(v));
    v[1] = 1;
    len = 0;
    if (dfs(1)) {
        path.clear();
        memset(v, 0, sizeof(v));
        v[1] = 1;
        path.push_back(1);
        search(1);
    }
    cout << "there are " << path.size() << "route to " << k;
}