DFS – 柳婼の blog

L3-007. 天梯地图-PAT团体程序设计天梯赛GPLT

本题要求你实现一个天梯赛专属在线地图，队员输入自己学校所在地和赛场地点后，该地图应该推荐两条路线：一条是最快到达路线；一条是最短距离的路线。题目保证对任意的查询请求，地图上都至少存在一条可达路线。

输入格式：

输入在第一行给出两个正整数N（2 <= N <=500）和M，分别为地图中所有标记地点的个数和连接地点的道路条数。随后M行，每行按如下格式给出一条道路的信息：

V1 V2 one-way length time

其中V1和V2是道路的两个端点的编号（从0到N-1）；如果该道路是从V1到V2的单行线，则one-way为1，否则为0；length是道路的长度；time是通过该路所需要的时间。最后给出一对起点和终点的编号。

输出格式：

首先按下列格式输出最快到达的时间T和用节点编号表示的路线：

Time = T: 起点 => 节点1 => … => 终点

然后在下一行按下列格式输出最短距离D和用节点编号表示的路线：

Distance = D: 起点 => 节点1 => … => 终点

如果最快到达路线不唯一，则输出几条最快路线中最短的那条，题目保证这条路线是唯一的。而如果最短距离的路线不唯一，则输出途径节点数最少的那条，题目保证这条路线是唯一的。

如果这两条路线是完全一样的，则按下列格式输出：

Time = T; Distance = D: 起点 => 节点1 => … => 终点

输入样例1：
10 15
0 1 0 1 1
8 0 0 1 1
4 8 1 1 1
5 4 0 2 3
5 9 1 1 4
0 6 0 1 1
7 3 1 1 2
8 3 1 1 2
2 5 0 2 2
2 1 1 1 1
1 5 0 1 3
1 4 0 1 1
9 7 1 1 3
3 1 0 2 5
6 3 1 2 1
5 3
输出样例1：
Time = 6: 5 => 4 => 8 => 3
Distance = 3: 5 => 1 => 3
输入样例2:
7 9
0 4 1 1 1
1 6 1 3 1
2 6 1 1 1
2 5 1 2 2
3 0 0 1 1
3 1 1 3 1
3 2 1 2 1
4 5 0 2 2
6 5 1 2 1
3 5
输出样例2:
Time = 3; Distance = 4: 3 => 2 => 5
分析：用两个Dijkstra + DFS。一个求最快路径（如果相同求路径的那条），一个求最短路径（如果相同求结点数最小的那条）～～求最快路径可以直接在Dijkstra里面求前驱结点Timepre数组~~~求最短路径因为要求结点数最小的那条，所以要用dispre的二维数组存储所有结点的最短路径，然后用DFS求出满足条件的结点数最小的那条～～

注意：
1.一开始最后一个测试用例“答案错误”，后来发现是自己在求最短路径（第二个答案distance）的时候忘记了temppath每一次深搜结束后的pop_back();
2.如果直接使用DFS的话，会导致最后一个测试用例“运行超时”～

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int inf = 999999999;
int dis[510], Time[510], e[510][510], w[510][510], Timepre[510], weight[510];
bool visit[510];
vector<int> Timepath, dispath, temppath, dispre[510];
int st, fin, minnode = inf;
void dfsTimepath(int v) {
    Timepath.push_back(v);
    if(v == st) {
        return ;
    }
    dfsTimepath(Timepre[v]);
}
void dfsdispath(int v) {
    temppath.push_back(v);
    if(v == st) {
        if(temppath.size() < minnode) {
            minnode = temppath.size();
            dispath = temppath;
        }
        temppath.pop_back();
        return ;
    }
    for(int i = 0; i < dispre[v].size(); i++) {
        dfsdispath(dispre[v][i]);
    }
    temppath.pop_back();
}
int main() {
    fill(dis, dis + 510, inf);
    fill(Time, Time + 510, inf);
    fill(weight, weight + 510, inf);
    fill(e[0], e[0] + 510 * 510, inf);
    fill(w[0], w[0] + 510 * 510, inf);
    int n, m;
    scanf("%d %d", &n, &m);
    int a, b, flag, len, t;
    for(int i = 0; i < m; i++) {
        scanf("%d %d %d %d %d", &a, &b, &flag, &len, &t);
        e[a][b] = len;
        w[a][b] = t;
        if(flag != 1) {
            e[b][a] = len;
            w[b][a] = t;
        }
    }
    scanf("%d %d", &st, &fin);
    Time[st] = 0;
    for(int i = 0; i < n; i++) {
        Timepre[i] = i;
    }
    for(int i = 0; i < n; i++) {
        int u = -1, minn = inf;
        for(int j = 0; j < n; j++) {
            if(visit[j] == false && Time[j] < minn) {
                u = j;
                minn = Time[j];
            }
        }
        if(u == -1) break;
        visit[u] = true;
        for(int v = 0; v < n; v++) {
            if(visit[v] == false && w[u][v] != inf) {
                if(w[u][v] + Time[u] < Time[v]) {
                    Time[v] = w[u][v] + Time[u];
                    Timepre[v] = u;
                    weight[v] = weight[u] + e[u][v];
                } else if(w[u][v] + Time[u] == Time[v] && weight[v] > weight[u] + e[u][v]) {
                    weight[v] = weight[u] + e[u][v];
                    Timepre[v] = u;
                }
            }
        }
    }
    dfsTimepath(fin);
    fill(visit, visit + 510, false);
    dis[st] = 0;
    for(int i = 0; i < n; i++) {
        int u = -1, minn = inf;
        for(int j = 0; j < n; j++) {
            if(visit[j] == false && minn > dis[j]) {
                u = j;
                minn = dis[j];
            }
        }
        if(u == -1) break;
        visit[u] = true;
        for(int v = 0; v < n; v++) {
            if(visit[v] == false && e[u][v] != inf) {
                if(e[u][v] + dis[u] < dis[v]) {
                    dis[v] = e[u][v] + dis[u];
                    dispre[v].clear();
                    dispre[v].push_back(u);
                } else if(e[u][v] + dis[u] == dis[v]) {
                    dispre[v].push_back(u);
                }
            }
        }
    }
    dfsdispath(fin);
    printf("Time = %d", Time[fin]);
    if(dispath == Timepath) {
        printf("; Distance = %d: ", dis[fin]);
    } else {
        printf(": ");
        for(int i = Timepath.size() - 1; i >= 0; i--) {
            printf("%d", Timepath[i]);
            if(i != 0) printf(" => ");
        }
        printf("\n");
        printf("Distance = %d: ", dis[fin]);
    }
    for(int i = dispath.size() - 1; i >= 0; i--) {
        printf("%d", dispath[i]);
        if(i != 0) printf(" => ");
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

#include <cstdio>

#include <algorithm>

#include <vector>

using namespace std;

const int inf = 999999999;

int dis[510], Time[510], e[510][510], w[510][510], Timepre[510], weight[510];

bool visit[510];

vector<int> Timepath, dispath, temppath, dispre[510];

int st, fin, minnode = inf;

void dfsTimepath(int v) {

Timepath.push_back(v);

if(v == st) {

return ;

}

dfsTimepath(Timepre[v]);

}

void dfsdispath(int v) {

temppath.push_back(v);

if(v == st) {

if(temppath.size() < minnode) {

minnode = temppath.size();

dispath = temppath;

}

temppath.pop_back();

return ;

}

for(int i = 0; i < dispre[v].size(); i++) {

dfsdispath(dispre[v][i]);

}

temppath.pop_back();

}

int main() {

fill(dis, dis + 510, inf);

fill(Time, Time + 510, inf);

fill(weight, weight + 510, inf);

fill(e[0], e[0] + 510 * 510, inf);

fill(w[0], w[0] + 510 * 510, inf);

int n, m;

scanf("%d %d", &n, &m);

int a, b, flag, len, t;

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

scanf("%d %d %d %d %d", &a, &b, &flag, &len, &t);

e[a][b] = len;

w[a][b] = t;

if(flag != 1) {

e[b][a] = len;

w[b][a] = t;

}

scanf("%d %d", &st, &fin);

Time[st] = 0;

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

Timepre[i] = i;

}

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

int u = -1, minn = inf;

for(int j = 0; j < n; j++) {

if(visit[j] == false && Time[j] < minn) {

u = j;

minn = Time[j];

}

if(u == -1) break;

visit[u] = true;

for(int v = 0; v < n; v++) {

if(visit[v] == false && w[u][v] != inf) {

if(w[u][v] + Time[u] < Time[v]) {

Time[v] = w[u][v] + Time[u];

Timepre[v] = u;

weight[v] = weight[u] + e[u][v];

} else if(w[u][v] + Time[u] == Time[v] && weight[v] > weight[u] + e[u][v]) {

weight[v] = weight[u] + e[u][v];

Timepre[v] = u;

}

dfsTimepath(fin);

fill(visit, visit + 510, false);

dis[st] = 0;

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

int u = -1, minn = inf;

for(int j = 0; j < n; j++) {

if(visit[j] == false && minn > dis[j]) {

u = j;

minn = dis[j];

}

if(u == -1) break;

visit[u] = true;

for(int v = 0; v < n; v++) {

if(visit[v] == false && e[u][v] != inf) {

if(e[u][v] + dis[u] < dis[v]) {

dis[v] = e[u][v] + dis[u];

dispre[v].clear();

dispre[v].push_back(u);

} else if(e[u][v] + dis[u] == dis[v]) {

dispre[v].push_back(u);

}

dfsdispath(fin);

printf("Time = %d", Time[fin]);

if(dispath == Timepath) {

printf("; Distance = %d: ", dis[fin]);

} else {

printf(": ");

for(int i = Timepath.size() - 1; i >= 0; i--) {

printf("%d", Timepath[i]);

if(i != 0) printf(" => ");

}

printf("\n");

printf("Distance = %d: ", dis[fin]);

}

for(int i = dispath.size() - 1; i >= 0; i--) {

printf("%d", dispath[i]);

if(i != 0) printf(" => ");

}

return 0;

}

1111. Online Map (30)-PAT甲级真题（Dijkstra + DFS）

Input our current position and a destination, an online map can recommend several paths. Now your job is to recommend two paths to your user: one is the shortest, and the other is the fastest. It is guaranteed that a path exists for any request.

Input Specification:

Each input file contains one test case. For each case, the first line gives two positive integers N (2 <= N <= 500), and M, being the total number of streets intersections on a map, and the number of streets, respectively. Then M lines follow, each describes a street in the format:

V1 V2 one-way length time

where V1 and V2 are the indices (from 0 to N-1) of the two ends of the street; one-way is 1 if the street is one-way from V1 to V2, or 0 if not; length is the length of the street; and time is the time taken to pass the street.

Finally a pair of source and destination is given.

Output Specification:

For each case, first print the shortest path from the source to the destination with distance D in the format:

Distance = D: source -> v1 -> … -> destination

Then in the next line print the fastest path with total time T:

Time = T: source -> w1 -> … -> destination

In case the shortest path is not unique, output the fastest one among the shortest paths, which is guaranteed to be unique. In case the fastest path is not unique, output the one that passes through the fewest intersections, which is guaranteed to be unique.

In case the shortest and the fastest paths are identical, print them in one line in the format:

Distance = D; Time = T: source -> u1 -> … -> destination

Sample Input 1:
10 15
0 1 0 1 1
8 0 0 1 1
4 8 1 1 1
3 4 0 3 2
3 9 1 4 1
0 6 0 1 1
7 5 1 2 1
8 5 1 2 1
2 3 0 2 2
2 1 1 1 1
1 3 0 3 1
1 4 0 1 1
9 7 1 3 1
5 1 0 5 2
6 5 1 1 2
3 5
Sample Output 1:
Distance = 6: 3 -> 4 -> 8 -> 5
Time = 3: 3 -> 1 -> 5
Sample Input 2:
7 9
0 4 1 1 1
1 6 1 1 3
2 6 1 1 1
2 5 1 2 2
3 0 0 1 1
3 1 1 1 3
3 2 1 1 2
4 5 0 2 2
6 5 1 1 2
3 5
Sample Output 2:
Distance = 3; Time = 4: 3 -> 2 -> 5

题目大意：给一张地图，两个结点中既有距离也有时间，有的单行有的双向，要求根据地图推荐两条路线：一条是最快到达路线，一条是最短距离的路线。
第一行给出两个整数N和M，表示地图中地点的个数和路径的条数。接下来的M行每一行给出：道路结点编号V1 道路结点编号V2 是否单行线道路长度所需时间
要求第一行输出最快到达时间Time和路径，第二行输出最短距离Distance和路径

分析：
1.用两个Dijkstra。一个求最短路径（如果相同求时间最短的那条），一个求最快路径（如果相同求结点数最小的那条）～～
2.求最短路径,和最快路径都可以在Dijkstra里面求前驱结点dispre和，Timepre数组～
3.dispre数组更新的条件是路径更短，或者路径相等的同时时间更短。
4.求最快路径时候要多维护一个NodeNum数组，记录在时间最短的情况下，到达此节点所需的节点数量。
Time数组更新的条件是，时间更短，时间相同的时候，如果此节点能让到达次节点是数目也变小，则更新Timepre，heNodeNum数组
5.最后根据dispre 和Timepre数组递归出两条路径，比较判断，输出最终答案～
注意：如果直接使用DFS的话，会导致最后一个测试用例“运行超时”～～

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int inf = 999999999;
int dis[510], Time[510], e[510][510], w[510][510], dispre[510],Timepre[510], weight[510],NodeNum[510];
bool visit[510];
vector<int> dispath, Timepath, temppath;
int st, fin, minnode = inf;
void dfsdispath(int v) {
    dispath.push_back(v);
    if(v == st) return ;
    dfsdispath(dispre[v]);
}
void dfsTimepath(int v) {
    Timepath.push_back(v);
    if(v == st) return ;
    dfsTimepath(Timepre[v]);
}
int main() {
    fill(dis, dis + 510, inf);
    fill(Time, Time + 510, inf);
    fill(weight, weight + 510, inf);
    fill(e[0], e[0] + 510 * 510, inf);
    fill(w[0], w[0] + 510 * 510, inf);
    int n, m;
    scanf("%d %d", &n, &m);
    int a, b, flag, len, t;
    for(int i = 0; i < m; i++) {
        scanf("%d %d %d %d %d", &a, &b, &flag, &len, &t);
        e[a][b] = len;
        w[a][b] = t;
        if(flag != 1) {
            e[b][a] = len;
            w[b][a] = t;
        }
    }
    scanf("%d %d", &st, &fin);
    dis[st] = 0;
    for(int i = 0; i < n; i++)
        dispre[i] = i;
    for(int i = 0; i < n; i++) {
        int u = -1, minn = inf;
        for(int j = 0; j < n; j++) {
            if(visit[j] == false && dis[j] < minn) {
                u = j;
                minn = dis[j];
            }
        }
        if(u == -1) break;
        visit[u] = true;
        for(int v = 0; v < n; v++) {
            if(visit[v] == false && e[u][v] != inf) {
                if(e[u][v] + dis[u] < dis[v]) {
                    dis[v] = e[u][v] + dis[u];
                    dispre[v] = u;
                    weight[v] = weight[u] + w[u][v];
                } else if(e[u][v] + dis[u] == dis[v] && weight[v] > weight[u] + w[u][v]) {
                    weight[v] = weight[u] + w[u][v];
                    dispre[v] = u;
                }
            }
        }
    }
    dfsdispath(fin);
    Time[st] = 0;
    fill(visit, visit + 510, false);
    for(int i = 0; i < n; i++) {
        int u = -1, minn = inf;
        for(int j = 0; j < n; j++) {
            if(visit[j] == false && minn > Time[j]) {
                u = j;
                minn = Time[j];
            }
        }
        if(u == -1) break;
        visit[u] = true;
        for(int v = 0; v < n; v++) {
            if(visit[v] == false && w[u][v] != inf) {
                if(w[u][v] + Time[u] < Time[v]) {
                    Time[v] = w[u][v] + Time[u];
                    Timepre[v]= u;
                    NodeNum[v]=NodeNum[u]+1;
                } else if(w[u][v] + Time[u] == Time[v]&&NodeNum[u]+1<NodeNum[v]) {
                    Timepre[v]= u;
                    NodeNum[v]=NodeNum[u]+1;
                }
            }
        }
    }
    dfsTimepath(fin);
    printf("Distance = %d", dis[fin]);
    if(dispath == Timepath) {
        printf("; Time = %d: ", Time[fin]);
    } else {
        printf(": ");
        for(int i = dispath.size() - 1; i >= 0; i--) {
            printf("%d", dispath[i]);
            if(i != 0) printf(" -> ");
        }
        printf("\nTime = %d: ", Time[fin]);
    }
    for(int i = Timepath.size() - 1; i >= 0; i--) {
        printf("%d", Timepath[i]);
        if(i != 0) printf(" -> ");
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

const int inf = 999999999;

int dis[510], Time[510], e[510][510], w[510][510], dispre[510],Timepre[510], weight[510],NodeNum[510];

bool visit[510];

vector<int> dispath, Timepath, temppath;

int st, fin, minnode = inf;

void dfsdispath(int v) {

dispath.push_back(v);

if(v == st) return ;

dfsdispath(dispre[v]);

}

void dfsTimepath(int v) {

Timepath.push_back(v);

if(v == st) return ;

dfsTimepath(Timepre[v]);

}

int main() {

fill(dis, dis + 510, inf);

fill(Time, Time + 510, inf);

fill(weight, weight + 510, inf);

fill(e[0], e[0] + 510 * 510, inf);

fill(w[0], w[0] + 510 * 510, inf);

int n, m;

scanf("%d %d", &n, &m);

int a, b, flag, len, t;

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

scanf("%d %d %d %d %d", &a, &b, &flag, &len, &t);

e[a][b] = len;

w[a][b] = t;

if(flag != 1) {

e[b][a] = len;

w[b][a] = t;

}

scanf("%d %d", &st, &fin);

dis[st] = 0;

for(int i = 0; i < n; i++)

dispre[i] = i;

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

int u = -1, minn = inf;

for(int j = 0; j < n; j++) {

if(visit[j] == false && dis[j] < minn) {

u = j;

minn = dis[j];

}

if(u == -1) break;

visit[u] = true;

for(int v = 0; v < n; v++) {

if(visit[v] == false && e[u][v] != inf) {

if(e[u][v] + dis[u] < dis[v]) {

dis[v] = e[u][v] + dis[u];

dispre[v] = u;

weight[v] = weight[u] + w[u][v];

} else if(e[u][v] + dis[u] == dis[v] && weight[v] > weight[u] + w[u][v]) {

weight[v] = weight[u] + w[u][v];

dispre[v] = u;

}

dfsdispath(fin);

Time[st] = 0;

fill(visit, visit + 510, false);

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

int u = -1, minn = inf;

for(int j = 0; j < n; j++) {

if(visit[j] == false && minn > Time[j]) {

u = j;

minn = Time[j];

}

if(u == -1) break;

visit[u] = true;

for(int v = 0; v < n; v++) {

if(visit[v] == false && w[u][v] != inf) {

if(w[u][v] + Time[u] < Time[v]) {

Time[v] = w[u][v] + Time[u];

Timepre[v]= u;

NodeNum[v]=NodeNum[u]+1;

} else if(w[u][v] + Time[u] == Time[v]&&NodeNum[u]+1<NodeNum[v]) {

Timepre[v]= u;

NodeNum[v]=NodeNum[u]+1;

}

dfsTimepath(fin);

printf("Distance = %d", dis[fin]);

if(dispath == Timepath) {

printf("; Time = %d: ", Time[fin]);

} else {

printf(": ");

for(int i = dispath.size() - 1; i >= 0; i--) {

printf("%d", dispath[i]);

if(i != 0) printf(" -> ");

}

printf("\nTime = %d: ", Time[fin]);

}

for(int i = Timepath.size() - 1; i >= 0; i--) {

printf("%d", Timepath[i]);

if(i != 0) printf(" -> ");

}

return 0;

}

1087. All Roads Lead to Rome (30)-PAT甲级真题（Dijkstra + DFS）

Indeed there are many different tourist routes from our city to Rome. You are supposed to find your clients the route with the least cost while gaining the most happiness.

Input Specification:
Each input file contains one test case. For each case, the first line contains 2 positive integers N (2<=N<=200), the number of cities, and K, the total number of routes between pairs of cities; followed by the name of the starting city. The next N-1 lines each gives the name of a city and an integer that represents the happiness one can gain from that city, except the starting city. Then K lines follow, each describes a route between two cities in the format “City1 City2 Cost”. Here the name of a city is a string of 3 capital English letters, and the destination is always ROM which represents Rome.

Output Specification:
For each test case, we are supposed to find the route with the least cost. If such a route is not unique, the one with the maximum happiness will be recommended. If such a route is still not unique, then we output the one with the maximum average happiness — it is guaranteed by the judge that such a solution exists and is unique.
Hence in the first line of output, you must print 4 numbers: the number of different routes with the least cost, the cost, the happiness, and the average happiness (take the integer part only) of the recommended route. Then in the next line, you are supposed to print the route in the format “City1->City2->…->ROM”.

Sample Input:
6 7 HZH
ROM 100
PKN 40
GDN 55
PRS 95
BLN 80
ROM GDN 1
BLN ROM 1
HZH PKN 1
PRS ROM 2
BLN HZH 2
PKN GDN 1
HZH PRS 1
Sample Output:
3 3 195 97
HZH->PRS->ROM

题目大意：有N个城市，M条无向边，从某个给定的起始城市出发，前往名为ROM的城市。每个城市（除了起始城市）都有一个点权（称为幸福值），和边权（每条边所需的花费）。求从起点到ROM所需要的最少花费，并输出其路径。如果路径有多条，给出幸福值最大的那条。如果仍然不唯一，选择路径上的城市平均幸福值最大的那条路径
分析：Dijkstra+DFS。Dijkstra算出所有最短路径的路线pre二维数组，DFS求最大happiness的路径path，并求出路径条数，最大happiness，最大average～
注意：average是除去起点的average。城市名称可以用m存储字符串所对应的数字，用m2存储数字对应的字符串

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
int n, k;
const int inf = 999999999;
int e[205][205], weight[205], dis[205];
bool visit[205];
vector<int> pre[205], temppath, path;
map<string, int> m;
map<int, string> m2;
int maxvalue = 0, mindepth, cntpath = 0;
double maxavg;
void dfs(int v) {
    temppath.push_back(v);
    if(v == 1) {
        int value = 0;
        for(int i = 0; i < temppath.size(); i++) {
            value += weight[temppath[i]];
        }
        double tempavg = 1.0 * value / (temppath.size() - 1);
        if(value > maxvalue) {
            maxvalue = value;
            maxavg = tempavg;
            path = temppath;
        } else if(value == maxvalue && tempavg > maxavg) {
            maxavg = tempavg;
            path = temppath;
        }
        temppath.pop_back();
        cntpath++;
        return ;
    }
    for(int i = 0; i < pre[v].size(); i++) {
        dfs(pre[v][i]);
    }
    temppath.pop_back();
}
int main() {
    fill(e[0], e[0] + 205 * 205, inf);
    fill(dis, dis + 205, inf);
    scanf("%d %d", &n, &k);
    string s;
    cin >> s;
    m[s] = 1;
    m2[1] = s;
    for(int i = 1; i < n; i++) {
        cin >> s >> weight[i+1];
        m[s] = i+1;
        m2[i+1] = s;
    }
    string sa, sb;
    int temp;
    for(int i = 0; i < k; i++) {
        cin >> sa >> sb >> temp;
        e[m[sa]][m[sb]] = temp;
        e[m[sb]][m[sa]] = temp;
    }
    dis[1] = 0;
    for(int i = 0; i < n; i++) {
        int u = -1, minn = inf;
        for(int j = 1; j <= n; j++) {
            if(visit[j] == false && dis[j] < minn) {
                u = j;
                minn = dis[j];
            }
        }
        if(u == -1) break;
        visit[u] = true;
        for(int v = 1; v <= n; v++) {
            if(visit[v] == false && e[u][v] != inf) {
                if(dis[u] + e[u][v] < dis[v]) {
                    dis[v] = dis[u] + e[u][v];
                    pre[v].clear();
                    pre[v].push_back(u);
                } else if(dis[v] == dis[u] + e[u][v]) {
                    pre[v].push_back(u);
                }
            }
        }
    }
    int rom = m["ROM"];
    dfs(rom);
    printf("%d %d %d %d\n", cntpath, dis[rom], maxvalue, (int)maxavg);
    for(int i = path.size() - 1; i >= 1; i--) {
        cout << m2[path[i]] << "->";
    }
    cout << "ROM";
    return 0;
}

#include <iostream>

#include <map>

#include <vector>

#include <algorithm>

using namespace std;

int n, k;

const int inf = 999999999;

int e[205][205], weight[205], dis[205];

bool visit[205];

vector<int> pre[205], temppath, path;

map<string, int> m;

map<int, string> m2;

int maxvalue = 0, mindepth, cntpath = 0;

double maxavg;

void dfs(int v) {

temppath.push_back(v);

if(v == 1) {

int value = 0;

for(int i = 0; i < temppath.size(); i++) {

value += weight[temppath[i]];

}

double tempavg = 1.0 * value / (temppath.size() - 1);

if(value > maxvalue) {

maxvalue = value;

maxavg = tempavg;

path = temppath;

} else if(value == maxvalue && tempavg > maxavg) {

maxavg = tempavg;

path = temppath;

}

temppath.pop_back();

cntpath++;

return ;

}

for(int i = 0; i < pre[v].size(); i++) {

dfs(pre[v][i]);

}

temppath.pop_back();

}

int main() {

fill(e[0], e[0] + 205 * 205, inf);

fill(dis, dis + 205, inf);

scanf("%d %d", &n, &k);

string s;

cin >> s;

m[s] = 1;

m2[1] = s;

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

cin >> s >> weight[i+1];

m[s] = i+1;

m2[i+1] = s;

}

string sa, sb;

int temp;

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

cin >> sa >> sb >> temp;

e[m[sa]][m[sb]] = temp;

e[m[sb]][m[sa]] = temp;

}

dis[1] = 0;

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

int u = -1, minn = inf;

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

if(visit[j] == false && dis[j] < minn) {

u = j;

minn = dis[j];

}

if(u == -1) break;

visit[u] = true;

for(int v = 1; v <= n; v++) {

if(visit[v] == false && e[u][v] != inf) {

if(dis[u] + e[u][v] < dis[v]) {

dis[v] = dis[u] + e[u][v];

pre[v].clear();

pre[v].push_back(u);

} else if(dis[v] == dis[u] + e[u][v]) {

pre[v].push_back(u);

}

int rom = m["ROM"];

dfs(rom);

printf("%d %d %d %d\n", cntpath, dis[rom], maxvalue, (int)maxavg);

for(int i = path.size() - 1; i >= 1; i--) {

cout << m2[path[i]] << "->";

}

cout << "ROM";

return 0;

}

LeetCode上Tag为深度优先搜索(Depth-frist Search)的题目整理

101. Symmetric Tree
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree is symmetric:
1
/ \
2 2
/ \ / \
3 4 4 3
But the following is not:
1
/ \
2 2
\ \
3 3
Note:
Bonus points if you could solve it both recursively and iteratively.
分析：这道题既可以用深度优先搜索DFS，也可以用广度优先搜索BFS。深度优先搜索的思路为：
传入root的左子树和右子树。如果两个都为NULL，则是对称的。如果两边都不为NULL并且两边的所对应的val相等，那就判断root->left->left和root->left->right是否对称，且判断root->left->right和root->right->left是否对称。。。
其余情况下return false;

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool func(TreeNode *left, TreeNode *right) {
        if(left == NULL && right == NULL)
            return true;
        if(left != NULL && right != NULL && left->val == right->val) {
            return func(left->left, right->right) && func(left->right, right->left);
        }
        return false;
    }
    bool isSymmetric(TreeNode* root) {
        if(root == NULL)
            return true;
        return func(root->left, root->right);
    }
};

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode(int x) : val(x), left(NULL), right(NULL) {}

* };

class Solution {

public:

bool func(TreeNode *left, TreeNode *right) {

if(left == NULL && right == NULL)

return true;

if(left != NULL && right != NULL && left->val == right->val) {

return func(left->left, right->right) && func(left->right, right->left);

}

return false;

}

bool isSymmetric(TreeNode* root) {

if(root == NULL)

return true;

return func(root->left, root->right);

}

};

257. Binary Tree Paths
Given a binary tree, return all root-to-leaf paths.
For example, given the following binary tree:

1
/ \
2 3
\
5
All root-to-leaf paths are:
[“1->2->5”, “1->3”]
分析：典型的深度优先搜索，dfs函数思路为：
dfs函数中参数传入一个string，该String将每次结点的值连接起来，直到递归出口的时候返回;
当该结点有左孩子的时候，将左孩子的值连接到字符串尾部;
当该结点有右孩子的时候，将右孩子的值连接到字符串尾部;
当该结点无左右孩子的时候，将字符串push入数组后return;

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void dfs(vector<string> &v, TreeNode *node, string s) {
        if(node->left == NULL && node->right == NULL) {
            v.push_back(s);
            return ;
        }
        if(node->left != NULL) {
            dfs(v, node->left, s + "->" + to_string(node->left->val));
        }
        if(node->right != NULL) {
            dfs(v, node->right, s + "->" + to_string(node->right->val));
        }
    }
    
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> v;
        if(root == NULL) {
            return v;
        }
        dfs(v, root, to_string(root->val));
        return v;
    }
};

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode(int x) : val(x), left(NULL), right(NULL) {}

* };

class Solution {

public:

void dfs(vector<string> &v, TreeNode *node, string s) {

if(node->left == NULL && node->right == NULL) {

v.push_back(s);

return ;

}

if(node->left != NULL) {

dfs(v, node->left, s + "->" + to_string(node->left->val));

}

if(node->right != NULL) {

dfs(v, node->right, s + "->" + to_string(node->right->val));

}

vector<string> binaryTreePaths(TreeNode* root) {

vector<string> v;

if(root == NULL) {

return v;

}

dfs(v, root, to_string(root->val));

return v;

}

};

100. Same Tree
Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.
分析：递归函数每次传入两棵树中的各一个结点。先传入两个树的root结点。若root结点均不为空，则判断这两个结点的值是否相等，和这两个结点的左孩子、右孩子是否相等~如果都满足则return true，否则return false~若传入的结点不是都不空的，判断是否同时都空~如果一个空一个不空那么是false~所以最后要加上一句return p == NULL && q == NULL;~~~~

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p != NULL && q != NULL)
            return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
        return p == NULL && q == NULL;
    }
};

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode(int x) : val(x), left(NULL), right(NULL) {}

* };

class Solution {

public:

bool isSameTree(TreeNode* p, TreeNode* q) {

if(p != NULL && q != NULL)

return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);

return p == NULL && q == NULL;

}

};

104. Maximum Depth of Binary Tree
Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
分析：分类讨论，设当前结点为root，如果root->left 和 root->right都为NULL，则返回1；
如果root->left不为NULL但是root->right为NULL，返回root->left为根节点的子树的最大层数+1；
如果root->right不为NULL但是root->left为NULL，返回root->right为根节点的子树的最大层数+1；
如果root->right和root->right都不为NULL，则返回以root->left为根节点的子树的层数和以root->right为根节点的子树的层数中的较大的那个值+1。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == NULL)
            return 0;
        if(root->left == NULL && root->right == NULL)
            return 1;
        if(root->left != NULL && root->right == NULL)
            return maxDepth(root->left) + 1;
        if(root->right != NULL && root->left == NULL)
            return maxDepth(root->right) + 1;
        int leftdepth = maxDepth(root->left);
        int rightdepth = maxDepth(root->right);
        return leftdepth > rightdepth ? leftdepth + 1 : rightdepth + 1;
    }
};

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode(int x) : val(x), left(NULL), right(NULL) {}

* };

class Solution {

public:

int maxDepth(TreeNode* root) {

if(root == NULL)

return 0;

if(root->left == NULL && root->right == NULL)

return 1;

if(root->left != NULL && root->right == NULL)

return maxDepth(root->left) + 1;

if(root->right != NULL && root->left == NULL)

return maxDepth(root->right) + 1;

int leftdepth = maxDepth(root->left);

int rightdepth = maxDepth(root->right);

return leftdepth > rightdepth ? leftdepth + 1 : rightdepth + 1;

}

};

110. Balanced Binary Tree
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
分析：判断一棵二叉树是否为平衡二叉树~设当前结点为root，设两个变量l和r分别表示以root为根节点的子树的左边的高度和右边的高度。如果root结点没有左孩子，那么l = 0；否则l = dfs(root->left)；如果root结点没有右孩子，那么r = 0；否则r = dfs(root->right)；以root为根节点的子树的高度为它的左边的高度l和右边的高度r两个中较大的那一个+1；当root根节点为空的时候，说明它的父结点的高度为1。如果l和r的绝对值大于等于2则返回false(在这里将标志flag置为0)。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int flag = 1;
    int dfs(TreeNode* root) {
        if(root == NULL)
            return 1;
        int l, r;
        if(root->left == NULL) {
           l = 0;
        } else {
           l = dfs(root->left);
        }
        if(root->right == NULL) {
           r = 0;
        } else {
           r = dfs(root->right);
        }
        if(abs(l-r) >= 2) {
            flag = 0;
        }
        return (l > r ? l : r) + 1;
    }
    bool isBalanced(TreeNode* root) {
        dfs(root);
        return flag;
    }
};

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode(int x) : val(x), left(NULL), right(NULL) {}

* };

class Solution {

public:

int flag = 1;

int dfs(TreeNode* root) {

if(root == NULL)

return 1;

int l, r;

if(root->left == NULL) {

l = 0;

} else {

l = dfs(root->left);

}

if(root->right == NULL) {

r = 0;

} else {

r = dfs(root->right);

}

if(abs(l-r) >= 2) {

flag = 0;

}

return (l > r ? l : r) + 1;

}

bool isBalanced(TreeNode* root) {

dfs(root);

return flag;

}

};

111. Minimum Depth of Binary Tree
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
分析：这道题即可以用深度优先，又可以用广度优先来做。这里用深度优先：
分析：分类讨论，设当前结点为root，如果root->left 和 root->right都为NULL，则返回1；
如果root->left不为NULL但是root->right为NULL，返回root->left为根节点的子树的最小层数+1；
如果root->right不为NULL但是root->left为NULL，返回root->right为根节点的子树的最小层数+1；
如果root->right和root->right都不为NULL，则返回以root->left为根节点的子树的层数和以root->right为根节点的子树的层数中的较小的那个值+1。

class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root == NULL)
            return 0;
        if(root->left == NULL && root->right == NULL)
            return 1;
        if(root->left == NULL && root->right != NULL)
            return minDepth(root->right) + 1;
        if(root->right == NULL && root->left != NULL)
            return minDepth(root->left) + 1;
        int leftdepth = minDepth(root->left);
        int rightdepth = minDepth(root->right);
        return leftdepth < rightdepth ? leftdepth + 1 : rightdepth + 1;
    }
};

class Solution {

public:

int minDepth(TreeNode* root) {

if(root == NULL)

return 0;

if(root->left == NULL && root->right == NULL)

return 1;

if(root->left == NULL && root->right != NULL)

return minDepth(root->right) + 1;

if(root->right == NULL && root->left != NULL)

return minDepth(root->left) + 1;

int leftdepth = minDepth(root->left);

int rightdepth = minDepth(root->right);

return leftdepth < rightdepth ? leftdepth + 1 : rightdepth + 1;

}

};

112. Path Sum
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
分析：如果当前结点root没有左孩子left并且没有右孩子right，并且sum == root->val则return true；否则的话将root的左孩子left和sum-root->val的剩余需要的值传入函数作为参数进一步检验~如果当前root == NULL 则return false；说明没有达到该路径和为sum的要求。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if(root == NULL)
            return false;
        if(root->left == NULL && root->right == NULL && sum == root->val)
                return true;
        return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
    }
};

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode(int x) : val(x), left(NULL), right(NULL) {}

* };

class Solution {

public:

bool hasPathSum(TreeNode* root, int sum) {

if(root == NULL)

return false;

if(root->left == NULL && root->right == NULL && sum == root->val)

return true;

return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);

}

};

还有几道深度优先：

POJ 1321-棋盘问题-简单搜索
在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。
Input 输入含有多组测试数据。
每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。
Output

对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。
Sample Input

2 1
#.
.#
4 4
…#
..#.
.#..
#…
-1 -1
Sample Output

2
1

#include <iostream>
using namespace std;
int col[10];
char pic[8][8];
int cou = 0;
int n, k;
void dfs(int begin, int num) {
    for (int j = 0; j < n; j++) {
        if (pic[begin][j] == '#' && col[j] == 0) {
            if (num == 1) {
                cou++;
            } else {
                col[j] = 1;
                for (int h = begin + 1; h <= n - num + 1; h++) {
                    dfs(h, num - 1);
                }
                col[j] = 0;
            }
        }
    }
}

int main() {
    while ((cin >> n >> k) && !(n == -1 && k == -1)) {
        cou = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> pic[i][j];
            }
        }
        for (int i = 0; i <= n - k; i++) {
            dfs(i, k);
        }
        cout << cou << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int col[10];

char pic[8][8];

int cou = 0;

int n, k;

void dfs(int begin, int num) {

for (int j = 0; j < n; j++) {

if (pic[begin][j] == '#' && col[j] == 0) {

if (num == 1) {

cou++;

} else {

col[j] = 1;

for (int h = begin + 1; h <= n - num + 1; h++) {

dfs(h, num - 1);

}

col[j] = 0;

}

int main() {

while ((cin >> n >> k) && !(n == -1 && k == -1)) {

cou = 0;

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

for (int j = 0; j < n; j++) {

cin >> pic[i][j];

}

for (int i = 0; i <= n - k; i++) {

dfs(i, k);

}

cout << cou << endl;

}

return 0;

}

POJ 1426-Find The Multiple-深度优先搜索dfs
Description
Given a positive integer n, write a program to find out a nonzero multiple m of n whose decimal representation contains only the digits 0 and 1. You may assume that n is not greater than 200 and there is a corresponding m containing no more than 100 decimal digits.
Input
The input file may contain multiple test cases. Each line contains a value of n (1 <= n <= 200). A line containing a zero terminates the input.
Output
For each value of n in the input print a line containing the corresponding value of m. The decimal representation of m must not contain more than 100 digits. If there are multiple solutions for a given value of n, any one of them is acceptable.
Sample Input
2
6
19
0
Sample Output
10
100100100100100100
111111111111111111

#include <iostream>
using namespace std;
int flag;
int n;
void dfs(unsigned long int t,int k) {
    if (flag == 1) 
        return ;
    if (t % n == 0) {
        cout << t << endl;
        flag = 1;
        return ;
    }
    if (k == 19) //到第19层还没找到那就回溯，别找了
        return ;
    dfs(t * 10, k + 1);
    dfs(t * 10 + 1, k + 1);
}
int main() {
    while (cin >> n && n != 0) {
        flag = 0;
        dfs(1, 0);
    }
}

#include <iostream>

using namespace std;

int flag;

int n;

void dfs(unsigned long int t,int k) {

if (flag == 1)

return ;

if (t % n == 0) {

cout << t << endl;

flag = 1;

return ;

}

if (k == 19) //到第19层还没找到那就回溯，别找了

return ;

dfs(t * 10, k + 1);

dfs(t * 10 + 1, k + 1);

}

int main() {

while (cin >> n && n != 0) {

flag = 0;

dfs(1, 0);

}

POJ-2488 A Knights Journey-深度优先搜索
The knight is getting bored of seeing the same black and white squares again and again and has decided to make a journey
around the world. Whenever a knight moves, it is two squares in one direction and one square perpendicular to this. The world of a knight is the chessboard he is living on. Our knight lives on a chessboard that has a smaller area than a regular 8 * 8 board, but it is still rectangular. Can you help this adventurous knight to make travel plans?

Problem
Find a path such that the knight visits every square once. The knight can start and end on any square of the board.
Input

The input begins with a positive integer n in the first line. The following lines contain n test cases. Each test case consists of a single line with two positive integers p and q, such that 1 <= p * q <= 26. This represents a p * q chessboard, where p describes how many different square numbers 1, . . . , p exist, q describes how many different square letters exist. These are the first q letters of the Latin alphabet: A, . . .
Output

The output for every scenario begins with a line containing “Scenario #i:”, where i is the number of the scenario starting at 1. Then print a single line containing the lexicographically first path that visits all squares of the chessboard with knight moves followed by an empty line. The path should be given on a single line by concatenating the names of the visited squares. Each square name consists of a capital letter followed by a number.
If no such path exist, you should output impossible on a single line.
Sample Input

3
1 1
2 3
4 3
Sample Output
Scenario #1:
A1
Scenario #2:
impossible
Scenario #3:
A1B3C1A2B4C2A3B1C3A4B2C4
Source
TUD Programming Contest 2005, Darmstadt, Germany

#include <iostream>
using namespace std;
int next1[8][2]={
    {-2, -1},
    {-2, 1},
    {-1, -2},
    {-1, 2},
    {1, -2},
    {1, 2},
    {2, -1},
    {2, 1}
};   //记录方向
int a, b, flag;
int book[26][26], path[26][2];
void dfs(int i, int j, int k) {
    if (k == a * b) {
        for (int t = 0; t < k; t++) {
            printf("%c", path[t][0] + 'A');
            cout << path[t][1]+1;
        }
        cout << endl;
        flag = 1;
    } else {
        for (int t = 0; t < 8; t++) {
            int n = i + next1[t][0];
            int m = j + next1[t][1];
            if (n >= 0 && n < b && m >= 0 && m < a && book[n][m] == 0 && flag == 0) {
                book[n][m] = 1;
                path[k][0] = n;
                path[k][1] = m;
                dfs(n, m, k + 1);
                book[n][m] = 0;
            }
        }
    }
}

int main() {
    int N;
    cin >> N;
    for (int m = 0; m < N; m++) {
        flag = 0;
        cin >> a >> b;
        for (int i = 0; i < a; i++)
            for (int j = 0; j < b; j++)
                book[i][j] = 0;
        book[0][0] = 1;
        path[0][0] = 0,path[0][1] = 0;
        cout << "Scenario #" << m + 1 << ":" << endl;
        dfs(0, 0, 1);
        if (!flag)
            cout << "impossible" << endl;
        cout << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int next1[8][2]={

{-2, -1},

{-2, 1},

{-1, -2},

{-1, 2},

{1, -2},

{1, 2},

{2, -1},

{2, 1}

}; //记录方向

int a, b, flag;

int book[26][26], path[26][2];

void dfs(int i, int j, int k) {

if (k == a * b) {

for (int t = 0; t < k; t++) {

printf("%c", path[t][0] + 'A');

cout << path[t][1]+1;

}

cout << endl;

flag = 1;

} else {

for (int t = 0; t < 8; t++) {

int n = i + next1[t][0];

int m = j + next1[t][1];

if (n >= 0 && n < b && m >= 0 && m < a && book[n][m] == 0 && flag == 0) {

book[n][m] = 1;

path[k][0] = n;

path[k][1] = m;

dfs(n, m, k + 1);

book[n][m] = 0;

}

int main() {

int N;

cin >> N;

for (int m = 0; m < N; m++) {

flag = 0;

cin >> a >> b;

for (int i = 0; i < a; i++)

for (int j = 0; j < b; j++)

book[i][j] = 0;

book[0][0] = 1;

path[0][0] = 0,path[0][1] = 0;

cout << "Scenario #" << m + 1 << ":" << endl;

dfs(0, 0, 1);

if (!flag)

cout << "impossible" << endl;

cout << endl;

}

return 0;

}

4.1 深度优先搜索
全排列 123456789 数字，输出第n个

#include <iostream>
using namespace std;
int book[10];
int a[10];
int n;
void dfs(int step) {
    if (step == n + 1) {
        for (int i = 1; i <= n; i++) {
            cout << a[i];
        }
        cout << endl;
        return;
    }

    for (int i = 1; i <= n; i++) {
        if (book[i] == 0) {
            a[step] = i;
            book[i] = 1;
            dfs(step + 1);
            book[i] = 0;
        }
    }
}

int main() {
    cin >> n;
    dfs(1);
    return 0;
}

#include <iostream>

using namespace std;

int book[10];

int a[10];

int n;

void dfs(int step) {

if (step == n + 1) {

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

cout << a[i];

}

cout << endl;

return;

}

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

if (book[i] == 0) {

a[step] = i;

book[i] = 1;

dfs(step + 1);

book[i] = 0;

}

int main() {

cin >> n;

dfs(1);

return 0;

}

4.1深度优先搜索-xxx + xxx = xxx

#include <iostream>
#include <cstdio>
using namespace std;

int a[10];
int book[10];
int total = 0;

int dfs(int step) {
    if (step == 10) {
        total++;
        if ((a[1] * 100 + a[2] * 10 + a[3] + a[4] * 100 + a[5] * 10 + a[6]) == (a[7] * 100 + a[8] * 10 + a[9])) {
            printf("%d%d%d + %d%d%d = %d%d%d", a[1], a[2], a[3], a[4], a[5], a[6], a[7], a[8], a[9]);
        }
        cout << endl;
        return;
    }

    for (int i = 1; i <= 9; i++) {
        if (book[i] == 0) {
            a[step] = 1; 
            book[i] = 1;
            dfs(step + 1);
            book[i] = 0;
        }
    }
}
int main() {
    dfs(1);
    cout << "total = " << total << endl;
    return 0;
}

#include <iostream>

#include <cstdio>

using namespace std;

int a[10];

int book[10];

int total = 0;

int dfs(int step) {

if (step == 10) {

total++;

if ((a[1] * 100 + a[2] * 10 + a[3] + a[4] * 100 + a[5] * 10 + a[6]) == (a[7] * 100 + a[8] * 10 + a[9])) {

printf("%d%d%d + %d%d%d = %d%d%d", a[1], a[2], a[3], a[4], a[5], a[6], a[7], a[8], a[9]);

}

cout << endl;

return;

}

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

if (book[i] == 0) {

a[step] = 1;

book[i] = 1;

dfs(step + 1);

book[i] = 0;

}

int main() {

dfs(1);

cout << "total = " << total << endl;

return 0;

}

4.2 深度优先搜索-迷宫最短路径
#include <iostream>
using namespace std;
int a[51][51];
int book[51][51];
int p, q;
int n, m;
int min1 = 999999;
void dfs(int x, int y, int step) {
    int next[4][2] = {
        {0, 1},
        {1, 0},
        {-1, 0},
        {0, -1}
    };
    int tx, ty;
    if (x == p && y == q) {
        if (step < min1) {
            min1 = step;
        }
        return;
    }

    for (int k = 0; k <= 3; k++) {
        tx = x + next[k][0];
        ty = y + next[k][1];

        if (tx < 1 || ty < 1 || tx > n || ty > m)
            continue;
        if (a[tx][ty] == 0 && book[tx][ty] == 0) {
            book[tx][ty] = 1;
            dfs(tx, ty, step + 1);
            book[tx][ty] = 0;
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    cin >> p >> q;
    int startx, starty;
    cin >> startx >> starty;
    book[startx][starty] = 1;
    dfs(startx, starty, 1);
    cout << min1;
    return 0;
}

4.2 深度优先搜索-迷宫最短路径

#include <iostream>

using namespace std;

int a[51][51];

int book[51][51];

int p, q;

int n, m;

int min1 = 999999;

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

int next[4][2] = {

{0, 1},

{1, 0},

{-1, 0},

{0, -1}

};

int tx, ty;

if (x == p && y == q) {

if (step < min1) {

min1 = step;

}

return;

}

for (int k = 0; k <= 3; k++) {

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

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

if (tx < 1 || ty < 1 || tx > n || ty > m)

continue;

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

book[tx][ty] = 1;

dfs(tx, ty, step + 1);

book[tx][ty] = 0;

}

int main() {

cin >> n >> m;

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

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

cin >> a[i][j];

}

cin >> p >> q;

int startx, starty;

cin >> startx >> starty;

book[startx][starty] = 1;

dfs(startx, starty, 1);

cout << min1;

return 0;

}

4.2 深度优先搜索-迷宫最短路径
#include <iostream>
using namespace std;
int a[51][51];
int book[51][51];
int p, q;
int n, m;
int min1 = 999999;
void dfs(int x, int y, int step) {
    int next[4][2] = {
        {0, 1},
        {1, 0},
        {-1, 0},
        {0, -1}
    };
    int tx, ty;
    if (x == p && y == q) {
        if (step < min1) {
            min1 = step;
        }
        return;
    }

    for (int k = 0; k <= 3; k++) {
        tx = x + next[k][0];
        ty = y + next[k][1];

        if (tx < 1 || ty < 1 || tx > n || ty > m)
            continue;
        if (a[tx][ty] == 0 && book[tx][ty] == 0) {
            book[tx][ty] = 1;
            dfs(tx, ty, step + 1);
            book[tx][ty] = 0;
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    cin >> p >> q;
    int startx, starty;
    cin >> startx >> starty;
    book[startx][starty] = 1;
    dfs(startx, starty, 1);
    cout << min1;
    return 0;
}

4.2 深度优先搜索-迷宫最短路径

#include <iostream>

using namespace std;

int a[51][51];

int book[51][51];

int p, q;

int n, m;

int min1 = 999999;

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

int next[4][2] = {

{0, 1},

{1, 0},

{-1, 0},

{0, -1}

};

int tx, ty;

if (x == p && y == q) {

if (step < min1) {

min1 = step;

}

return;

}

for (int k = 0; k <= 3; k++) {

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

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

if (tx < 1 || ty < 1 || tx > n || ty > m)

continue;

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

book[tx][ty] = 1;

dfs(tx, ty, step + 1);

book[tx][ty] = 0;

}

int main() {

cin >> n >> m;

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

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

cin >> a[i][j];

}

cin >> p >> q;

int startx, starty;

cin >> startx >> starty;

book[startx][starty] = 1;

dfs(startx, starty, 1);

cout << min1;

return 0;

}

4.5.2 深度优先搜索-宝岛探险
#include <iostream>
using namespace std;
int a[51][51];
int book[51][51];//全局变量自动全部初始化为0
int n, m;
int sum = 0;

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

void dfs(int x, int y) {
    int tx, ty;
    for (int k = 0; k <= 3; k++) {
        tx = x + next[k][0];
        ty = y + next[k][1];

        if (tx < 1 || tx > n || ty < 1 || ty > m)
            continue;
        if (a[tx][ty] > 0 && book[tx][ty] == 0) {
            book[tx][ty] = 1;
            sum++;
            dfs(tx, ty);
        }
    }
    return ;
}

int main() {
    int startx, starty;
    cin >> n >> m >> startx >> starty;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];

    dfs(startx, starty);
    cout << sum;
    
    return 0;
}

4.5.2 深度优先搜索-宝岛探险

#include <iostream>

using namespace std;

int a[51][51];

int book[51][51];//全局变量自动全部初始化为0

int n, m;

int sum = 0;

int next[4][2] = {

{1, 0};

{0, 1};

{-1, 0};

{0, -1}

};

void dfs(int x, int y) {

int tx, ty;

for (int k = 0; k <= 3; k++) {

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

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

if (tx < 1 || tx > n || ty < 1 || ty > m)

continue;

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

book[tx][ty] = 1;

sum++;

dfs(tx, ty);

}

return ;

}

int main() {

int startx, starty;

cin >> n >> m >> startx >> starty;

for (int i = 1; i <= n; i++)

for (int j = 1; j <= m; j++)

cin >> a[i][j];

dfs(startx, starty);

cout << sum;

return 0;

}

5.1.1 图的深度优先搜索
上面讲的深度和广度优先搜索都是对一个矩阵方格纸的。
#include <iostream>
using namespace std;
int book[101];
int sum = 0;
int n, e[101][101];

void dfs(int cur) {
    cout << cur << " "; //输出当前所在顶点的编号，当作是当前遍历到了这个结点
    sum++; //遍历到的节点数目+1
    if (sum == n)
        return ; //如果所有顶点都已经访问过那就直接退出

    for (int i = 1; i <= n; i++) {
        if (e[cur][i] == 1 && book[i] == 0) {
            book[i] = 1;
            dfs(i);
        }
    }
    return ;
}
int main() {
    int m; //m是边的个数，n是结点的个数
    int a, b;//储存每条边的两个结点的临时变量
    //初始化二维矩阵
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            if (i == j)
                e[i][j] = 0;
            else
                e[i][j] = 99999999;
        }

    //读入边
    for (int i = 1; i <= m; i++) {
        cin >> a >> b;
        e[a][b] = 1;
        e[b][a] = 1;
    }

    book[1] = 1;
    dfs(1); //从结点1开始出发

    return 0;
}

5.1.1 图的深度优先搜索

上面讲的深度和广度优先搜索都是对一个矩阵方格纸的。

#include <iostream>

using namespace std;

int book[101];

int sum = 0;

int n, e[101][101];

void dfs(int cur) {

cout << cur << " "; //输出当前所在顶点的编号，当作是当前遍历到了这个结点

sum++; //遍历到的节点数目+1

if (sum == n)

return ; //如果所有顶点都已经访问过那就直接退出

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

if (e[cur][i] == 1 && book[i] == 0) {

book[i] = 1;

dfs(i);

}

return ;

}

int main() {

int m; //m是边的个数，n是结点的个数

int a, b;//储存每条边的两个结点的临时变量

//初始化二维矩阵

for (int i = 1; i <= n; i++)

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

if (i == j)

e[i][j] = 0;

else

e[i][j] = 99999999;

}

//读入边

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

cin >> a >> b;

e[a][b] = 1;

e[b][a] = 1;

}

book[1] = 1;

dfs(1); //从结点1开始出发

return 0;

}

5.2 单源最短路径-图的深度优先遍历
#include <iostream>
using namespace std;
int min = 99999999;
int book[101];
int n;
int e[101][101];

//dis是当前所在的城市编号，dis是当前已经走过的路程
void dfs(int cur, int dis) {
    if (dis > min)
        return ;
    if (cur == n) {
        if (dis < min) 
            min = dis;
        return ;
    }

    for (int i = 1; i <= n; i++) {
        if (e[cur][i] != 99999999 && book[i] == 0) {
            book[i] = 1;
            dfs(i, dis + e[cur][i]);
            book[i] = 0;
        }
    }
    return ;
}

int main() {
    int m;
    cin >> n >> m;
    int a, b, c;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            if (i == j)
                e[i][j] = 0;
            else
                e[i][j] = 99999999;
        }

    book[1] = 1;
    dfs(1, 0);
    cout << min;

    return 0;
}

5.2 单源最短路径-图的深度优先遍历

#include <iostream>

using namespace std;

int min = 99999999;

int book[101];

int n;

int e[101][101];

//dis是当前所在的城市编号，dis是当前已经走过的路程

void dfs(int cur, int dis) {

if (dis > min)

return ;

if (cur == n) {

if (dis < min)

min = dis;

return ;

}

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

if (e[cur][i] != 99999999 && book[i] == 0) {

book[i] = 1;

dfs(i, dis + e[cur][i]);

book[i] = 0;

}

return ;

}

int main() {

int m;

cin >> n >> m;

int a, b, c;

for (int i = 1; i <= n; i++)

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

if (i == j)

e[i][j] = 0;

else

e[i][j] = 99999999;

}

book[1] = 1;

dfs(1, 0);

cout << min;

return 0;

}