Code – 第236页

蓝桥杯 BASIC-23 基础练习芯片测试

问题描述
有n（2≤n≤20）块芯片，有好有坏，已知好芯片比坏芯片多。
每个芯片都能用来测试其他芯片。用好芯片测试其他芯片时，能正确给出被测试芯片是好还是坏。而用坏芯片测试其他芯片时，会随机给出好或是坏的测试结果（即此结果与被测试芯片实际的好坏无关）。
给出所有芯片的测试结果，问哪些芯片是好芯片。
输入格式
输入数据第一行为一个整数n，表示芯片个数。
第二行到第n+1行为n*n的一张表，每行n个数据。表中的每个数据为0或1，在这n行中的第i行第j列（1≤i, j≤n）的数据表示用第i块芯片测试第j块芯片时得到的测试结果，1表示好，0表示坏，i=j时一律为1（并不表示该芯片对本身的测试结果。芯片不能对本身进行测试）。
输出格式
按从小到大的顺序输出所有好芯片的编号
样例输入
3
1 0 1
0 1 0
1 0 1
样例输出
1 3
分析：因为超过半数的芯片是好的，所以这些芯片对于其他芯片的测试结果是正确的。
所以假设该芯片是好芯片，它除了它自身测试自身之外的其他测试结果为好的个数将超过一半。
同理，假设该芯片是坏芯片，他将有超过半数的测试结果是坏芯片。
所以只要根据每一列的所有测试结果，判断其为好芯片的总数>=n/2的时候，这个芯片就是好芯片。

#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    int a[20][20];
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }
    for(int i = 0; i < n; i++) {
        int cnt = 0;
        for(int j = 0; j < n; j++) {
            if(j != i)
                cnt += a[j][i];
        }
        if(cnt >= n/2) {
            cout << i+1 << " ";
        }
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

int a[20][20];

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

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

cin >> a[i][j];

}

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

int cnt = 0;

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

if(j != i)

cnt += a[j][i];

}

if(cnt >= n/2) {

cout << i+1 << " ";

}

return 0;

}

蓝桥杯 BASIC-24 基础练习龟兔赛跑预测

问题描述
　　话说这个世界上有各种各样的兔子和乌龟，但是研究发现，所有的兔子和乌龟都有一个共同的特点——喜欢赛跑。于是世界上各个角落都不断在发生着乌龟和兔子的比赛，小华对此很感兴趣，于是决定研究不同兔子和乌龟的赛跑。他发现，兔子虽然跑比乌龟快，但它们有众所周知的毛病——骄傲且懒惰，于是在与乌龟的比赛中，一旦任一秒结束后兔子发现自己领先t米或以上，它们就会停下来休息s秒。对于不同的兔子，t，s的数值是不同的，但是所有的乌龟却是一致——它们不到终点决不停止。
　　然而有些比赛相当漫长，全程观看会耗费大量时间，而小华发现只要在每场比赛开始后记录下兔子和乌龟的数据——兔子的速度v1（表示每秒兔子能跑v1米），乌龟的速度v2，以及兔子对应的t，s值，以及赛道的长度l——就能预测出比赛的结果。但是小华很懒，不想通过手工计算推测出比赛的结果，于是他找到了你——清华大学计算机系的高才生——请求帮助，请你写一个程序，对于输入的一场比赛的数据v1，v2，t，s，l，预测该场比赛的结果。
输入格式
　　输入只有一行，包含用空格隔开的五个正整数v1，v2，t，s，l，其中(v1,v2<=100;t<=300;s<=10;l<=10000且为v1,v2的公倍数)
输出格式
　　输出包含两行，第一行输出比赛结果——一个大写字母“T”或“R”或“D”，分别表示乌龟获胜，兔子获胜，或者两者同时到达终点。
　　第二行输出一个正整数，表示获胜者（或者双方同时）到达终点所耗费的时间（秒数）。
样例输入
10 5 5 2 20
样例输出
D
4
样例输入
10 5 5 1 20
样例输出
R
3
样例输入
10 5 5 3 20
样例输出
T
4

#include <iostream>
using namespace std;
int main() {
	int vr, vt, t, s, l;
	cin >> vr >> vt >> t >> s >> l;
	int ttime = l / vt;
	int cnttime = 0;
	int lent = 0;
	int lenr = 0;
	int breaktime = 0;//统计兔子休息的时间
	int flag = 0;//flag==0表示兔子不在休息，flag==1表示兔子正在休息
	while(lent < l && lenr < l) {
		if(flag == 0 && lenr - lent < t || flag == 1 && breaktime >= s) {
			lenr = lenr + vr;
			flag = 0;
			breaktime = 0;
		} else {
			flag = 1;
			breaktime++;
		}
		lent = lent + vt;
		cnttime++;
	}
	if(lent >= l && lenr < l) {
		cout << "T" << endl;
	} else if(lent < l && lenr >= l) {
		cout << "R" << endl;
	} else {
		cout << "D" << endl;
	}
	cout << cnttime;
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int vr, vt, t, s, l;

cin >> vr >> vt >> t >> s >> l;

int ttime = l / vt;

int cnttime = 0;

int lent = 0;

int lenr = 0;

int breaktime = 0;//统计兔子休息的时间

int flag = 0;//flag==0表示兔子不在休息，flag==1表示兔子正在休息

while(lent < l && lenr < l) {

if(flag == 0 && lenr - lent < t || flag == 1 && breaktime >= s) {

lenr = lenr + vr;

flag = 0;

breaktime = 0;

} else {

flag = 1;

breaktime++;

}

lent = lent + vt;

cnttime++;

}

if(lent >= l && lenr < l) {

cout << "T" << endl;

} else if(lent < l && lenr >= l) {

cout << "R" << endl;

} else {

cout << "D" << endl;

}

cout << cnttime;

return 0;

}

蓝桥杯 BASIC-25 基础练习回形取数

问题描述
　　回形取数就是沿矩阵的边取数，若当前方向上无数可取或已经取过，则左转90度。一开始位于矩阵左上角，方向向下。
输入格式
　　输入第一行是两个不超过200的正整数m, n，表示矩阵的行和列。接下来m行每行n个整数，表示这个矩阵。
输出格式
　　输出只有一行，共mn个数，为输入矩阵回形取数得到的结果。数之间用一个空格分隔，行末不要有多余的空格。
样例输入
3 3
1 2 3
4 5 6
7 8 9
样例输出
1 4 7 8 9 6 3 2 5
样例输入
3 2
1 2
3 4
5 6
样例输出
1 3 5 6 4 2

#include <iostream>
#include <memory.h>
using namespace std;
int main() {
    int m, n;
    cin >> m >> n;
    int a[201][201];
    memset(a, -1, sizeof(a));
    int i = 0, j = 0;
    for(i = 0; i < m; i++)
        for(j = 0; j < n; j++)
            cin >> a[i][j];
    i = 0, j = 0;
    int total = 0;
    while(total < m * n) {
        while(i <= m-1 && a[i][j] != -1) {//down
            cout << a[i][j] << " ";
            a[i][j] = -1;
            i++;
            total++;
        }
        i--;
        j++;
        while(j <= n-1 && a[i][j] != -1) {//right
            cout << a[i][j] << " ";
            a[i][j] = -1;
            j++;
            total++;
        }
        j--;
        i--;
        while(i >= 0 && a[i][j] != -1) {//up
            cout << a[i][j] << " ";
            a[i][j] = -1;
            i--;
            total++;
        }
        i++;
        j--;
        while(j >= 0 && a[i][j] != -1) {//left
            cout << a[i][j] << " ";
            a[i][j] = -1;
            j--;
            total++;
        }
        j++;
        i++;
    } 
    return 0;
}

#include <iostream>

#include <memory.h>

using namespace std;

int main() {

int m, n;

cin >> m >> n;

int a[201][201];

memset(a, -1, sizeof(a));

int i = 0, j = 0;

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

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

cin >> a[i][j];

i = 0, j = 0;

int total = 0;

while(total < m * n) {

while(i <= m-1 && a[i][j] != -1) {//down

cout << a[i][j] << " ";

a[i][j] = -1;

i++;

total++;

}

i--;

j++;

while(j <= n-1 && a[i][j] != -1) {//right

cout << a[i][j] << " ";

a[i][j] = -1;

j++;

total++;

}

j--;

i--;

while(i >= 0 && a[i][j] != -1) {//up

cout << a[i][j] << " ";

a[i][j] = -1;

i--;

total++;

}

i++;

j--;

while(j >= 0 && a[i][j] != -1) {//left

cout << a[i][j] << " ";

a[i][j] = -1;

j--;

total++;

}

j++;

i++;

}

return 0;

}

蓝桥杯BASIC-28 基础练习 Huffuman树

问题描述
　　Huffman树在编码中有着广泛的应用。在这里，我们只关心Huffman树的构造过程。
　　给出一列数{pi}={p0, p1, …, pn-1}，用这列数构造Huffman树的过程如下：
　　1. 找到{pi}中最小的两个数，设为pa和pb，将pa和pb从{pi}中删除掉，然后将它们的和加入到{pi}中。这个过程的费用记为pa + pb。
　　2. 重复步骤1，直到{pi}中只剩下一个数。
　　在上面的操作过程中，把所有的费用相加，就得到了构造Huffman树的总费用。
　　本题任务：对于给定的一个数列，现在请你求出用该数列构造Huffman树的总费用。

　　例如，对于数列{pi}={5, 3, 8, 2, 9}，Huffman树的构造过程如下：
　　1. 找到{5, 3, 8, 2, 9}中最小的两个数，分别是2和3，从{pi}中删除它们并将和5加入，得到{5, 8, 9, 5}，费用为5。
　　2. 找到{5, 8, 9, 5}中最小的两个数，分别是5和5，从{pi}中删除它们并将和10加入，得到{8, 9, 10}，费用为10。
　　3. 找到{8, 9, 10}中最小的两个数，分别是8和9，从{pi}中删除它们并将和17加入，得到{10, 17}，费用为17。
　　4. 找到{10, 17}中最小的两个数，分别是10和17，从{pi}中删除它们并将和27加入，得到{27}，费用为27。
　　5. 现在，数列中只剩下一个数27，构造过程结束，总费用为5+10+17+27=59。
输入格式
　　输入的第一行包含一个正整数n（n<=100）。
　　接下来是n个正整数，表示p0, p1, …, pn-1，每个数不超过1000。
输出格式
　　输出用这些数构造Huffman树的总费用。
样例输入
5
5 3 8 2 9
样例输出
59

#include <iostream>
#include <vector>
#include <algorithm>
int cmp1(int a, int b) {
    return a > b;
}
using namespace std;
int main() {
    int n;
    int price = 0;
    vector<int> v;
    cin >> n;
    for(int i = 0; i < n; i++) {
        int temp;
        cin >> temp;
        v.push_back(temp);
    }
    int size = v.size();
    while(size >= 2) {
        sort(v.begin(), v.end(), cmp1);
        int t = v[size-1] + v[size-2];
        price += t;
        v.pop_back();
        v.pop_back();
        v.push_back(t);
        size = v.size();
    }
    cout << price;
    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

int cmp1(int a, int b) {

return a > b;

}

using namespace std;

int main() {

int n;

int price = 0;

vector<int> v;

cin >> n;

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

int temp;

cin >> temp;

v.push_back(temp);

}

int size = v.size();

while(size >= 2) {

sort(v.begin(), v.end(), cmp1);

int t = v[size-1] + v[size-2];

price += t;

v.pop_back();

v.push_back(t);

size = v.size();

}

cout << price;

return 0;

}

蓝桥杯-基础练习十六进制转八进制

问题描述
给定n个十六进制正整数，输出它们对应的八进制数。
输入格式
输入的第一行为一个正整数n （1<=n<=10）。
接下来n行，每行一个由0~9、大写字母A~F组成的字符串，表示要转换的十六进制正整数，每个十六进制数长度不超过100000。
输出格式
输出n行，每行为输入对应的八进制正整数。
【注意】
输入的十六进制数不会有前导0，比如012A。
输出的八进制数也不能有前导0。
样例输入
2
39
123ABC
样例输出
71
4435274
【提示】
先将十六进制数转换成某进制数，再由某进制数转换成八进制。
分析：先转成二进制，然后按3的倍数在前面补上0，然后转为对应的八进制，记得前面如果有0要去掉~

#include <iostream>
#include <map>
using namespace std;
int main() {
    string b, s, a;
    int n;
    cin >> n;
    string arr[16] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000",
        "1001", "1010", "1011", "1100", "1101", "1110", "1111"};
    map<string, string> m;
    m["000"] = "0"; m["001"] = "1"; m["010"] = "2"; m["011"] = "3"; m["100"] = "4";
    m["101"] = "5"; m["110"] = "6"; m["111"] = "7";
    for(int i = 0; i < n; i++) {
        cin >> s;
        int lens = s.length();
        for(int j = 0; j < lens; j++) {
            if(s[j] > '9') {
                b += arr[s[j] - 'A' + 10];
            } else {
                b += arr[s[j] - '0'];
            }
        }
        int lenb = b.length();
        if(lenb % 3 == 1) {
            b = "00" + b;
        } else if(lenb % 3 == 2) {
            b = "0" + b;
        }
        int flag = 0;
        for(int j = 0; j < lenb; j += 3) {
            string temp = b.substr(j, 3);
            string t = m[temp];
            if(j == 0 && t == "0") {
                flag = 1;
                continue;
            }
            if(flag == 1 && j == 3 && t == "0") {
                continue;
            }
            cout << t;
        }
        cout << endl;
        b = "";
    }
    return 0;
}

#include <iostream>

#include <map>

using namespace std;

int main() {

string b, s, a;

int n;

cin >> n;

string arr[16] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000",

"1001", "1010", "1011", "1100", "1101", "1110", "1111"};

map<string, string> m;

m["000"] = "0"; m["001"] = "1"; m["010"] = "2"; m["011"] = "3"; m["100"] = "4";

m["101"] = "5"; m["110"] = "6"; m["111"] = "7";

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

cin >> s;

int lens = s.length();

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

if(s[j] > '9') {

b += arr[s[j] - 'A' + 10];

} else {

b += arr[s[j] - '0'];

}

int lenb = b.length();

if(lenb % 3 == 1) {

b = "00" + b;

} else if(lenb % 3 == 2) {

b = "0" + b;

}

int flag = 0;

for(int j = 0; j < lenb; j += 3) {

string temp = b.substr(j, 3);

string t = m[temp];

if(j == 0 && t == "0") {

flag = 1;

continue;

}

if(flag == 1 && j == 3 && t == "0") {

continue;

}

cout << t;

}

cout << endl;

b = "";

}

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;

}