liuchuo – 第239页 – 我不管，反正我最萌～

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;

}

LeetCode 103. Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]

分析：和层序遍历一样的代码，只需要加几行代码就行～～因为要之字型存储这个二叉树～～所以只不过在行数为双数的时候需要对当前行进行一次所有元素的倒置～可以用stack也可以用数组头尾两两交换的方法～只需要在存入二维数组vector<vector> v之前倒置好row数组，再push_back到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:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<int> row;
        vector<vector<int>> v;
        queue<TreeNode *> q;
        if(root == NULL)
            return v;
        q.push(root);
        TreeNode *temp;
        int lev = 0;
        while(!q.empty()) {
            int size = q.size();
            while(size--) {
                temp = q.front();
                q.pop();
                row.push_back(temp->val);
                if(temp->left != NULL) {
                    q.push(temp->left);
                }
                if(temp->right != NULL) {
                    q.push(temp->right);
                }
            }
            if(lev % 2) {
                int n = row.size();
                for(int i = 0; i < n/2; i++) {
                    swap(row[i], row[n-i-1]);
                }
            }
            v.push_back(row);
            lev++;
            row.clear();
        }
        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:

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {

vector<int> row;

vector<vector<int>> v;

queue<TreeNode *> q;

if(root == NULL)

return v;

q.push(root);

TreeNode *temp;

int lev = 0;

while(!q.empty()) {

int size = q.size();

while(size--) {

temp = q.front();

q.pop();

row.push_back(temp->val);

if(temp->left != NULL) {

q.push(temp->left);

}

if(temp->right != NULL) {

q.push(temp->right);

}

if(lev % 2) {

int n = row.size();

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

swap(row[i], row[n-i-1]);

}

v.push_back(row);

lev++;

row.clear();

}

return v;

}

};

LeetCode199. Binary Tree Right Side View

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
For example:
Given the following binary tree,
1 <—
/ \
2 3 <—
\ \
5 4 <—
You should return [1, 3, 4].

分析：这道题可以用广度优先搜索也可以用深度优先搜索。这里用广度优先方法解决：
如果root为空，则返回空vector。建立存放TreeNode指针的队列，将root结点入队；出队root的同时入队root的存在的left和right结点；按照层序遍历的方式，把每一层的最后一个结点的值存入vector中，最后返回vector～

/**
 * 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:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> v;
        queue<TreeNode*> q;
        if(root == NULL)
            return v;
        q.push(root);
        TreeNode* h;
        while(!q.empty()) {
            int size = q.size();
            while(size--) {
                h = q.front();
                q.pop();
                if(h->left != NULL)
                    q.push(h->left);
                if(h->right != NULL)
                    q.push(h->right);
            }
            v.push_back(h->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:

vector<int> rightSideView(TreeNode* root) {

vector<int> v;

queue<TreeNode*> q;

if(root == NULL)

return v;

q.push(root);

TreeNode* h;

while(!q.empty()) {

int size = q.size();

while(size--) {

h = q.front();

q.pop();

if(h->left != NULL)

q.push(h->left);

if(h->right != NULL)

q.push(h->right);

}

v.push_back(h->val);

}

return v;

}

};

LeetCode上Tag为广度优先搜索BFS(Breadth-first 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.
分析：这道题既可以用深度优先搜索，也可以用广度优先搜索。此处先用广度优先搜索来做。
建立两个队列，lq和rq，每次比较队首的两个元素是否相等。
lq队列的队首l出列后，将它的left和right分别入队；
rq队列的队首r出列后，将它的right和left分别入队。
因为判断是否对称是这样比较的：
l->left 与 r->right
l->right 与 r->left比较。

/**
 * 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 isSymmetric(TreeNode* root) {
        if(root == NULL)
            return true;
        queue<TreeNode*> lq, rq;
        if(root->left != NULL)
            lq.push(root->left);
        if(root->right != NULL)
            rq.push(root->right);
        TreeNode *l, *r;
        while(!lq.empty() && !rq.empty()) {
            l = lq.front();
            lq.pop();
            r = rq.front();
            rq.pop();
            if(l == NULL && r == NULL)
                continue;
            if(l == NULL || r == NULL || l->val != r->val)
                return false;
            lq.push(l->left);
            rq.push(r->right);
            lq.push(l->right);
            rq.push(r->left);
        }
        if(lq.empty() && rq.empty())
            return true;
        else
            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 isSymmetric(TreeNode* root) {

if(root == NULL)

return true;

queue<TreeNode*> lq, rq;

if(root->left != NULL)

lq.push(root->left);

if(root->right != NULL)

rq.push(root->right);

TreeNode *l, *r;

while(!lq.empty() && !rq.empty()) {

l = lq.front();

lq.pop();

r = rq.front();

rq.pop();

if(l == NULL && r == NULL)

continue;

if(l == NULL || r == NULL || l->val != r->val)

return false;

lq.push(l->left);

rq.push(r->right);

lq.push(l->right);

rq.push(r->left);

}

if(lq.empty() && rq.empty())

return true;

else

return false;

}

};

102. Binary Tree Level Order Traversal
Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).
For example:
Given binary tree {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
分析：二叉树的层序遍历，使用广度优先搜索，建立一个队列q。
每次将队首temp结点出队列的同时，将temp的左孩子和右孩子入队
用size标记入队后的队列长度
row数组始终为当前层的遍历结果，然后用while(size–)语句保证每一次保存入row的只有一层。
每一次一层遍历完成后，将该row的结果存入二维数组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:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<int> row;
        vector<vector<int>> v;
        queue<TreeNode *> q;
        if(root == NULL)
            return v;
        q.push(root);
        TreeNode *temp;
        while(!q.empty()) {
            int size = q.size();
            while(size--) {
                temp = q.front();
                q.pop();
                row.push_back(temp->val);
                if(temp->left != NULL) {
                    q.push(temp->left);
                }
                if(temp->right != NULL) {
                    q.push(temp->right);
                }
            }
            v.push_back(row);
            row.clear();
        }
        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:

vector<vector<int>> levelOrder(TreeNode* root) {

vector<int> row;

vector<vector<int>> v;

queue<TreeNode *> q;

if(root == NULL)

return v;

q.push(root);

TreeNode *temp;

while(!q.empty()) {

int size = q.size();

while(size--) {

temp = q.front();

q.pop();

row.push_back(temp->val);

if(temp->left != NULL) {

q.push(temp->left);

}

if(temp->right != NULL) {

q.push(temp->right);

}

v.push_back(row);

row.clear();

}

return v;

}

};

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.
分析：这道题既可以用广度优先搜索，又可以用深度优先搜索。这里用广度优先搜索解决。
建立一个存储结点的队列q。设指针p指向队首。将p出队的同时将p->left和p->right入队~
若发现p既没有left结点也没有right结点（就是说p是叶子结点）的时候直接return ans
否则在每一层遍历完成后ans++;
和上一题层序遍历相似，只是在层序遍历的过程中加入了判断是否已经是叶子结点。如果是叶子结点就直接返回当前的层数~

/**
 * 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 minDepth(TreeNode* root) {
        if(root == NULL)
            return 0;
        queue<TreeNode *> q;
        q.push(root);
        TreeNode* p;
        int ans = 1;  
        while(!q.empty()) {
            int size = q.size();
            while(size--) {
                p = q.front();
                if(p->left == NULL && p->right == NULL)
                    return ans;
                if(p->left != NULL) 
                    q.push(p->left);
                if(p->right != NULL)
                    q.push(p->right);
                q.pop();
            }
            ans++;
        }
        return ans;
    }
};

/**

* 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 minDepth(TreeNode* root) {

if(root == NULL)

return 0;

queue<TreeNode *> q;

q.push(root);

TreeNode* p;

int ans = 1;

while(!q.empty()) {

int size = q.size();

while(size--) {

p = q.front();

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

return ans;

if(p->left != NULL)

q.push(p->left);

if(p->right != NULL)

q.push(p->right);

q.pop();

}

ans++;

}

return ans;

}

};

279. Perfect Squares
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.
For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.
分析：这道题既可以用动态规划的方法来做，又可以用广度优先搜索的方法做。这里先用广度优先搜索的方法来做。
建立一个队列，并把n入队~~这个时候从后往前检索所有平方小于n的数，并把他们逐一入队；然后将temp值为队首的值，再从后往前检索所有平方小于temp的数，并把他们逐一入队。。直到有一次入队时候发现该数字为0时return。
比如设13为根节点，13 – 3 * 3 = 4， 13 – 2 * 2 = 9， 13 – 1 * 1 = 12，
4， 9， 12就是root的三个child，是第二层；
再下面一层，4 – 2 * 2 = 0， 4 – 1 * 1 = 3，4的child是0和3
因为发现了一个0，说明此时该层就为该数最少需要的平方和数字的个数~~

class Solution {
public:
    int numSquares(int n) {
        queue<int> q;
        q.push(n);
        int ans = 1;
        while(!q.empty()) {
            int size = q.size();
            while(size--) {
                int temp = q.front();
                q.pop();
                for(int i = sqrt(temp); i >= 1; i--) {
                    if(i*i == temp)
                        return ans;
                    q.push(temp-i*i);
                }
            }
            ans++;
        }
        return ans;
    }
};

class Solution {

public:

int numSquares(int n) {

queue<int> q;

q.push(n);

int ans = 1;

while(!q.empty()) {

int size = q.size();

while(size--) {

int temp = q.front();

q.pop();

for(int i = sqrt(temp); i >= 1; i--) {

if(i*i == temp)

return ans;

q.push(temp-i*i);

}

ans++;

}

return ans;

}

};

199. Binary Tree Right Side View
Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
For example:
Given the following binary tree,
1 <—
/ \
2 3 <—
\ \
5 4 <—
You should return [1, 3, 4].
分析：这道题可以用广度优先搜索也可以用深度优先搜索。这里用广度优先方法解决：
如果root为空，则返回空vector。
建立存放TreeNode指针的队列，将root结点入队；
出队root的同时入队root的存在的left和right结点；
按照层序遍历的方式，把每一层的最后一个结点的值存入vector中，最后返回vector。

/**
 * 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:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> v;
        queue<TreeNode*> q;
        if(root == NULL)
            return v;
        q.push(root);
        TreeNode* h;
        while(!q.empty()) {
            int size = q.size();
            while(size--) {
                h = q.front();
                q.pop();
                if(h->left != NULL)
                    q.push(h->left);
                if(h->right != NULL)
                    q.push(h->right);
            }
            v.push_back(h->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:

vector<int> rightSideView(TreeNode* root) {

vector<int> v;

queue<TreeNode*> q;

if(root == NULL)

return v;

q.push(root);

TreeNode* h;

while(!q.empty()) {

int size = q.size();

while(size--) {

h = q.front();

q.pop();

if(h->left != NULL)

q.push(h->left);

if(h->right != NULL)

q.push(h->right);

}

v.push_back(h->val);

}

return v;

}

};

103. Binary Tree Zigzag Level Order Traversal
Given a binary tree, return the zigzag level order traversal of its nodes values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]
分析：和层序遍历一样的代码，只需要加几行代码就行~~~因为要之字型存储这个二叉树~~~所以只不过在行数为双数的时候需要对当前行进行一次所有元素的倒置~可以用stack也可以用数组头尾两两交换的方法~~只需要在存入二维数组vector<vector> v之前倒置好row数组，再push_back到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:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<int> row;
        vector<vector<int>> v;
        queue<TreeNode *> q;
        if(root == NULL)
            return v;
        q.push(root);
        TreeNode *temp;
        int lev = 0;
        while(!q.empty()) {
            int size = q.size();
            while(size--) {
                temp = q.front();
                q.pop();
                row.push_back(temp->val);
                if(temp->left != NULL) {
                    q.push(temp->left);
                }
                if(temp->right != NULL) {
                    q.push(temp->right);
                }
            }
            if(lev % 2) {
                int n = row.size();
                for(int i = 0; i < n/2; i++) {
                    swap(row[i], row[n-i-1]);
                }
            }
            v.push_back(row);
            lev++;
            row.clear();
        }
        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:

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {

vector<int> row;

vector<vector<int>> v;

queue<TreeNode *> q;

if(root == NULL)

return v;

q.push(root);

TreeNode *temp;

int lev = 0;

while(!q.empty()) {

int size = q.size();

while(size--) {

temp = q.front();

q.pop();

row.push_back(temp->val);

if(temp->left != NULL) {

q.push(temp->left);

}

if(temp->right != NULL) {

q.push(temp->right);

}

if(lev % 2) {

int n = row.size();

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

swap(row[i], row[n-i-1]);

}

v.push_back(row);

lev++;

row.clear();

}

return v;

}

};

再上一道POJ上面的题目：
POJ 3126-Prime Path-广度优先搜索bfs
The ministers of the cabinet were quite upset by the message from the Chief of Security stating that they would all have to change the four-digit room numbers on their offices.
— It is a matter of security to change such things every now and then, to keep the enemy in the dark.
— But look, I have chosen my number 1033 for good reasons. I am the Prime minister, you know!
— I know, so therefore your new number 8179 is also a prime. You will just have to paste four new digits over the four old ones on your office door.
— No, it’s not that simple. Suppose that I change the first digit to an 8, then the number will read 8033 which is not a prime!
— I see, being the prime minister you cannot stand having a non-prime number on your door even for a few seconds.
— Correct! So I must invent a scheme for going from 1033 to 8179 by a path of prime numbers where only one digit is changed from one prime to the next prime.

Now, the minister of finance, who had been eavesdropping, intervened.
— No unnecessary expenditure, please! I happen to know that the price of a digit is one pound.
— Hmm, in that case I need a computer program to minimize the cost. You do not know some very cheap software gurus, do you?
— In fact, I do. You see, there is this programming contest going on… Help the prime minister to find the cheapest prime path between any two given four-digit primes! The first digit must be nonzero, of course. Here is a solution in the case above.
1033
1733
3733
3739
3779
8779
8179
The cost of this solution is 6 pounds. Note that the digit 1 which got pasted over in step 2 can not be reused in the last step – a new 1 must be purchased.
Input
One line with a positive number: the number of test cases (at most 100). Then for each test case, one line with two numbers separated by a blank. Both numbers are four-digit primes (without leading zeros).
Output
One line for each case, either with a number stating the minimal cost or containing the word Impossible.
Sample Input
3
1033 8179
1373 8017
1033 1033
Sample Output
6
7
0

#include <iostream>
#include <cmath> //sqrt()函数

using namespace std;
int a, b;
bool book[15000];//book用来标记该数字有没有使用过,book是标记的意思啦。
struct node {
    int num;
    int step;
};
struct node queue[15000];

bool isprime(int x) {
    if (x == 2 || x == 3)
        return 1;
    else if (x % 2 == 0 || x <= 1)
        return 0;
    else if (x > 3) {
        for (int i = 3; i <= sqrt((double)x); i += 2) {//一开始直接写的sqrt(x),Compile Error 了，查了一下发现sqrt只支持 float double 和 long double 三个原型，果断改成了sqrt((double)x)。不过当然也可以用i * i <= x 啦。
            if (x % i == 0)
                return 0;
        }
    }
    return 1;
}

void bfs() {
    int head = 0;
    int tail = 0;
    queue[tail].num = a;
    queue[tail].step = 0;
    book[a] = true;
    tail++;
    
    while (head < tail) {
        if (queue[head].num == b) {
            cout << queue[head].step << endl;
            return ;
        }
        
        int first = queue[head].num % 10;
        int second = queue[head].num / 10 % 10;
        //个位
        for (int i = 1; i <= 9; i += 2) { //个位数如果是偶数一定是不符合的，所以这里写 i += 2
            int c = queue[head].num / 10 * 10 + i;
            if (!book[c] && isprime(c) && c != queue[head].num) {
                queue[tail].num = c;
                queue[tail].step = queue[head].step + 1;//是在head的step基础上加1啊啊啊啊啊
                book[c] = true;
                tail++;
            }
        }
        
        //十位
        for (int i = 0; i <= 9; i++) {
            int c = queue[head].num / 100 * 100 + i * 10 + first;
            if (!book[c] && isprime(c) && c != queue[head].num) {
                queue[tail].num = c;
                queue[tail].step = queue[head].step + 1;//是在head的step基础上加1啊啊啊啊啊
                book[c] = true;
                tail++;
            }
        }
        
        //百位
        for (int i = 0; i <= 9; i++) {
            int c = queue[head].num / 1000 * 1000 + i * 100 + second * 10 + first;
            if (!book[c] && isprime(c) && c != queue[head].num) {
                queue[tail].num = c;
                queue[tail].step = queue[head].step + 1;//是在head的step基础上加1啊啊啊啊啊
                book[c] = true;
                tail++;
            }
        }
        
        //千位
        for (int i = 1; i <= 9; i++) {
            int c = queue[head].num % 1000 + i * 1000;
            if (!book[c] && isprime(c) && c != queue[head].num) {
                queue[tail].num = c;
                queue[tail].step = queue[head].step + 1;//是在head的step基础上加1啊啊啊啊啊
                book[c] = true;
                tail++;
            }
        }
        head++;
    }
    cout << "Impossible" << endl;
    return ;
}

int main() {
    int n;
    cin >> n;
    while (n--) {
        cin >> a >> b;
        memset(book, false, sizeof(book));
        bfs();
    }
    return 0;
}

100

101

#include <iostream>

#include <cmath> //sqrt()函数

using namespace std;

int a, b;

bool book[15000];//book用来标记该数字有没有使用过,book是标记的意思啦。

struct node {

int num;

int step;

};

struct node queue[15000];

bool isprime(int x) {

if (x == 2 || x == 3)

return 1;

else if (x % 2 == 0 || x <= 1)

return 0;

else if (x > 3) {

for (int i = 3; i <= sqrt((double)x); i += 2) {//一开始直接写的sqrt(x),Compile Error 了，查了一下发现sqrt只支持 float double 和 long double 三个原型，果断改成了sqrt((double)x)。不过当然也可以用i * i <= x 啦。

if (x % i == 0)

return 0;

}

return 1;

}

void bfs() {

int head = 0;

int tail = 0;

queue[tail].num = a;

queue[tail].step = 0;

book[a] = true;

tail++;

while (head < tail) {

if (queue[head].num == b) {

cout << queue[head].step << endl;

return ;

}

int first = queue[head].num % 10;

int second = queue[head].num / 10 % 10;

//个位

for (int i = 1; i <= 9; i += 2) { //个位数如果是偶数一定是不符合的，所以这里写 i += 2

int c = queue[head].num / 10 * 10 + i;

if (!book[c] && isprime(c) && c != queue[head].num) {

queue[tail].num = c;

queue[tail].step = queue[head].step + 1;//是在head的step基础上加1啊啊啊啊啊

book[c] = true;

tail++;

}

//十位

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

int c = queue[head].num / 100 * 100 + i * 10 + first;

if (!book[c] && isprime(c) && c != queue[head].num) {

queue[tail].num = c;

queue[tail].step = queue[head].step + 1;//是在head的step基础上加1啊啊啊啊啊

book[c] = true;

tail++;

}

//百位

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

int c = queue[head].num / 1000 * 1000 + i * 100 + second * 10 + first;

if (!book[c] && isprime(c) && c != queue[head].num) {

queue[tail].num = c;

queue[tail].step = queue[head].step + 1;//是在head的step基础上加1啊啊啊啊啊

book[c] = true;

tail++;

}

//千位

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

int c = queue[head].num % 1000 + i * 1000;

if (!book[c] && isprime(c) && c != queue[head].num) {

queue[tail].num = c;

queue[tail].step = queue[head].step + 1;//是在head的step基础上加1啊啊啊啊啊

book[c] = true;

tail++;

}

head++;

}

cout << "Impossible" << endl;

return ;

}

int main() {

int n;

cin >> n;

while (n--) {

cin >> a >> b;

memset(book, false, sizeof(book));

bfs();

}

return 0;

}

POJ 3278-Catch That Cow-广度优先搜索
Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 ≤ N ≤ 100,000) on a number line and the cow is at a point K (0 ≤ K ≤ 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting.
* Walking: FJ can move from any point X to the points X – 1 or X + 1 in a single minute
* Teleporting: FJ can move from any point X to the point 2 × X in a single minute.
If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?
Input
Line 1: Two space-separated integers: N and K
Output
Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.
Sample Input
5 17
Sample Output
4
Hint
The fastest way for Farmer John to reach the fugitive cow is to move along the following path: 5-10-9-18-17, which takes 4 minutes.

#include <iostream>
#include <queue>
#include <memory.h>

using namespace std;
#define MAX 100005

queue<int> q;
int step[MAX];
bool visit[MAX];
int n, k;
int head, tail;

int bfs() {
    q.push(n);
    step[n] = 0;
    visit[n] = 1;
    while (!q.empty()) {
        head = q.front();
        q.pop();

        for (int i = 0; i < 3; i++) {
            if(i == 0)
                tail = head - 1;
            else if (i == 1)
                tail = head + 1;
            else
                tail = head * 2;
            if (tail > MAX || tail < 0)
                continue;
            if (!visit[tail]) {
                q.push(tail);
                step[tail] = step[head] + 1;
                visit[tail] = 1;
            }
            if(tail == k)
                return step[tail];
        }
    }
    return -1;
}
int main() {
    memset(visit, 0, sizeof(visit));
    cin >> n >> k;
    if (n > k) {
        cout << n - k;
    } else {
        cout << bfs();
    }
    return 0;
}

#include <iostream>

#include <queue>

#include <memory.h>

using namespace std;

#define MAX 100005

queue<int> q;

int step[MAX];

bool visit[MAX];

int n, k;

int head, tail;

int bfs() {

q.push(n);

step[n] = 0;

visit[n] = 1;

while (!q.empty()) {

head = q.front();

q.pop();

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

if(i == 0)

tail = head - 1;

else if (i == 1)

tail = head + 1;

else

tail = head * 2;

if (tail > MAX || tail < 0)

continue;

if (!visit[tail]) {

q.push(tail);

step[tail] = step[head] + 1;

visit[tail] = 1;

}

if(tail == k)

return step[tail];

}

return -1;

}

int main() {

memset(visit, 0, sizeof(visit));

cin >> n >> k;

if (n > k) {

cout << n - k;

} else {

cout << bfs();

}

return 0;

}

还有一道蓝桥杯上的题目：
学霸的迷宫-算法提高
问题描述
　　学霸抢走了大家的作业，班长为了帮同学们找回作业，决定去找学霸决斗。但学霸为了不要别人打扰，住在一个城堡里，城堡外面是一个二维的格子迷宫，要进城堡必须得先通过迷宫。因为班长还有妹子要陪，磨刀不误砍柴功，他为了节约时间，从线人那里搞到了迷宫的地图，准备提前计算最短的路线。可是他现在正向妹子解释这件事情，于是就委托你帮他找一条最短的路线。
输入格式
　　第一行两个整数n， m，为迷宫的长宽。
　　接下来n行，每行m个数，数之间没有间隔，为0或1中的一个。0表示这个格子可以通过，1表示不可以。假设你现在已经在迷宫坐标(1,1)的地方，即左上角，迷宫的出口在(n,m)。每次移动时只能向上下左右4个方向移动到另外一个可以通过的格子里，每次移动算一步。数据保证(1,1)，(n,m)可以通过。
输出格式
　　第一行一个数为需要的最少步数K。
　　第二行K个字符，每个字符∈{U,D,L,R},分别表示上下左右。如果有多条长度相同的最短路径，选择在此表示方法下字典序最小的一个。
样例输入
Input Sample 1:
3 3
001
100
110

Input Sample 2:
3 3
000
000
000
样例输出
Output Sample 1:
4
RDRD

Output Sample 2:
4
DDRR
数据规模和约定
　　有20%的数据满足：1<=n,m<=10
　　有50%的数据满足：1<=n,m<=50
　　有100%的数据满足：1<=n,m<=500。

#include <iostream>
using namespace std;
struct note {
    int x;
    int y;
    int f;
    int s;
    char dir;
};

int main() {
    char a[501][501];
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
        getchar();
    }
    int head = 1;
    int tail = 1;
    int book[501][501] = {0};
    book[1][1] = 1;
    
    int next[4][2] = {
        {1, 0},
        {0, -1},
        {0, 1},
        {-1, 0}
    };
    int tx = 1;
    int ty = 1;
    
    struct note que[250001];
    que[tail].x = 1;
    que[tail].y = 1;
    que[tail].f = 0;
    que[tail].s = 0;
    tail++;
    int flag = 0;
    while (head < tail) {
        for (int k = 0; k <= 3; k++) {
            tx = que[head].x + next[k][0];
            ty = que[head].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;
                que[tail].x = tx;
                que[tail].y = ty;
                que[tail].f = head;
                que[tail].s = que[head].s + 1;
                if (k == 0) que[tail].dir = 'D';
                else if (k == 1) que[tail].dir = 'L';
                else if (k == 2) que[tail].dir = 'R';
                else if (k == 3) que[tail].dir = 'U';
                tail++;
            }
            if (tx == n && ty == m) {
                flag = 1;
                break;
            }
        }
        if (flag == 1) {
            break;
        }
        head++;
    }
    cout << que[tail - 1].s << endl;
    char t[250001];
    int temp = tail - 1;
    for (int i = que[tail - 1].s; i >= 1; i--) {
        t[i] = que[temp].dir;
        temp = que[temp].f;
    }
    for (int i = 1; i <= que[tail - 1].s; i++) {
        cout << t[i];
    }
    return 0;
}

#include <iostream>

using namespace std;

struct note {

int x;

int y;

int f;

int s;

char dir;

};

int main() {

char a[501][501];

int n, m;

cin >> n >> m;

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

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

cin >> a[i][j];

}

getchar();

}

int head = 1;

int tail = 1;

int book[501][501] = {0};

book[1][1] = 1;

int next[4][2] = {

{1, 0},

{0, -1},

{0, 1},

{-1, 0}

};

int tx = 1;

int ty = 1;

struct note que[250001];

que[tail].x = 1;

que[tail].y = 1;

que[tail].f = 0;

que[tail].s = 0;

tail++;

int flag = 0;

while (head < tail) {

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

tx = que[head].x + next[k][0];

ty = que[head].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;

que[tail].x = tx;

que[tail].y = ty;

que[tail].f = head;

que[tail].s = que[head].s + 1;

if (k == 0) que[tail].dir = 'D';

else if (k == 1) que[tail].dir = 'L';

else if (k == 2) que[tail].dir = 'R';

else if (k == 3) que[tail].dir = 'U';

tail++;

}

if (tx == n && ty == m) {

flag = 1;

break;

}

if (flag == 1) {

break;

}

head++;

}

cout << que[tail - 1].s << endl;

char t[250001];

int temp = tail - 1;

for (int i = que[tail - 1].s; i >= 1; i--) {

t[i] = que[temp].dir;

temp = que[temp].f;

}

for (int i = 1; i <= que[tail - 1].s; i++) {

cout << t[i];

}

return 0;

}

【汇编】JMP跳转指令的指令长度、直接转移与间接转移、段内跳转与段间跳转

指令长度=操作码的长度+操作数地址的长度
1.段内跳转
JMP指令占1个字节。
操作数的地址长度 = （目标地址-指令当前地址）//若能用1个字节表示，则占用1个字节,那么整体指令长度为2个字节;若需2个字节表示，则占用2个字节，此时整体指令为3个字节。
比如：
0113 jmp 0185 ;0185h-0113h=72h，72h可用1个字节表示，加上JMP的一个字节，一共指令长度为2个字节；
0113 jmp 0845 ;0845h-0113h=732h，732h需用2个字节表示，加上JMP的一个字节，一共指令长度为3个字节。

2、段间跳转
指令长度为5字节。如jmp 1234:5678，整体指令长度为5.

直接转移 IP = 位移量 + 指令长度
间接转移 IP = 寻址方式求出的EA(有效地址)的值

直接转移中
短转移JMP SHORT OPR 8位位移量
位移量需要满足前后跳转的需要，所以是一个带符号数 转移格式只允许在-128~127之间转移
近转移JMP NEAR PTR OPR 16/32位位移量
16位在实模式下段长为64KB，所以16位位移量可以转移到段内的任一个位置

《追寻生命的意义》读书笔记

2016-05-12 10:14:42
在精神病学中有一种所谓的“暂缓性迷惑”的症状。行将被处决的人在被执行之前有时会获得一种可能在最后一刻暂缓执行的幻觉。我们也抱有这种希望，直到最后一刻还认为情况可能不至于太糟。那些囚徒红润的脸膛和胖乎乎的圆脸就是一大鼓励。当时，我们都不知道，他们是一群精英，日复一日地跑到车站，充当着接待新来者的专门队伍。他们负责管理新来的人及其行李，包括稀有物品和被抢劫的珠宝。

2016-05-12 10:15:32

3个囚徒被关进了至多可容纳200人的棚屋里。我们又冷又饿，而且非常拥挤，我们几乎无法蹲下，更不用说躺着了。一块五盎司重的面包是我们四天中的惟一食物。

2016-05-12 10:24:38

然后，他说道，“我将给你们两分钟，并且，我将用表给你们计时。在这两分钟之内，你们必须脱去所有的衣服，并把所有的东西放在你正站立着的地上。除了鞋、皮带和吊带，或者捆扎带之外，你们不能带走任何东西。现在，我开始计时—开始!”
人们以不可思议的飞快速度脱去了外套。随着时间的临近，他们也变得越来越紧张，笨拙地忙于脱去内衣、裤带和鞋带。然后，我们听见了鞭子的第一次响声;皮带打在了赤裸裸的身体上。

2016-05-12 10:26:11

我们一些人仍然怀有的幻想就这样一个接一个地被破灭了，并且，非常出人意料地，我们多数人都被一种冷酷的幽默感所战胜。我们知道，除了可笑的赤裸裸的生命之外，我们已经没有任何东西可以失去。当淋浴开始时，我们都使劲地开玩笑，既取笑自己也相互取笑。

2016-05-12 10:28:15

我想顺便提出一些对于我们能够承受多大痛苦的惊奇:我们无法刷牙且严重缺乏维生素，但是，我们的胃却比以前更健康。半年以来，我们不得不穿同一件衬衣，直到它完全失去衬衣的外观。许多天以来，由于自来水管冻结，我们一直不能洗漱，甚至连部分擦洗也不可能。双手因在土里干活而肮脏不堪，但手上的疮和擦伤却从不化脓(也就是说，除非有冻疮)。一些人原来睡眠很浅，隔壁房间的一丝响动都可能搅得他不得安宁，但是现在他却能够与一位离他耳朵几英寸、妍声震天的囚徒挤在一起，在噪音中沉沉人睡。

2016-05-12 10:28:49

现在，如果有人问我们，托斯绥夫斯基把人定义为可以习惯任何事物的观点是否正确，我们将回答:“是的，人能够习惯任何事物，但是，不要问我们，人是如何习惯的。”

2016-05-12 10:29:55

如果把一瞬间的想法也算进去的话，我们每个人都曾有过自杀的念头。死亡的潜在危险和现实无时不在，无处不有，使得生活情形天生就带着一种绝望。从我将要提及的个人信念出发，在进人集中营的第一个晚.上，我就坚定地立下了誓言，我将永远不会去“碰铁丝网”。这是一个集中营用语，用来描述最常用的自杀方法—碰撞带电的带刺铁丝网。就我而言，作出自杀的决定毫无困难。自杀没有任何意义，因为对于普通囚徒来说，客观估计并加上所有的偶然性，活下来的可能性也是微乎其微。他没有任何把握成为闯过所有选择的极少部分人中的一员。奥斯维辛集中营的囚徒在惊恐的第一阶段就不俱怕死亡。在最初的几天之后，至毒气室都不再恐怖—毕竟，毒气室能使他免除自杀的麻烦。

2016-05-12 10:32:32

他继续说，“如果可能的话，每天刮脸，即使你不得不用玻璃去刮，·一即使你不得不用最后一块面包去换。这样，你将会看起来很年
轻，而且，刮脸还使你的脸看起来更红润。如果你想活下来，只有一个办法:看起来适合干活。如果你瘸了，由子，让我说下去，你的脚后跟上有一个水疙，如果党卫军看见你这样，他就会把你招到一边。第二天，你肯定将被送进毒气室。看起来悲惨可怜、落魄潦倒、患病瘦弱、不再能干重体力活的人，总有一夭，通常是在不久之后，都要被送进毒气室。因此牢牢地记住:刮脸、神气而有力地站立和行走;于是，你就不用害怕毒气了。

2016-05-12 10:32:55

这一反应在几天之后开始发生变化。囚徒从第一阶段进人了第二阶段;一种相对冷漠的阶段，在此期间，他获得了某种程度的情感死亡。

2016-05-12 10:36:26

冷漠、感情迟钝，以及人们不再关心任何事情的感觉，是产生于囚徒心理反应第二阶段的症状，并最终使他对于时时刻刻的殴打折磨无动于衷。通过这一无动于衷的感觉，囚徒们用一种非常必要的保护性外壳将自己严严实实地包裹起来。

2016-05-12 10:38:08

十分奇怪的是，在某些情况下，没有留下痕迹的打击甚至比留下痕迹的更加疼痛。有一次，我站立在暴风雪中的铁路上。天气虽然恶劣，但是我们仍要不停地干活。我卖力地用碎石修补路基，因为这是保持身体温暖的惟一办法。我停了下来，靠着铁锹喘了日气，也就一会儿的功夫，然而，倒霉的是，正在这时，看守转过身来，发现我在偷懒:他对我的伤害不是来自于侮辱和拳打脚踢。这个看守认为，不值得向站在前面的这位衣衫破烂、瘦骨嶙峋的家伙说一句话，甚至不值得咒骂、相反地，他顽皮地捡起一块石头并向我扔了过来。在我看来，这似乎是一种办法，用来吸引野兽注意，吹喝家畜干活，一种与你几乎没有共同之处的生物，以至于你甚至不愿意惩罚它。

2016-05-12 10:43:23

有些工头会同情我们，并尽力改善我们的处境，至少是在工地上。但是，即使他们也不断地提醒我们，一名正常的工人可以做几倍于我们的一作，而且所用的时间更短。但是，他们并不知道，正常工人并不以每天十又二分之一盎司的面包(理论上的—实际上，我们常常吃得比这更少)和一又三分之一品脱的汤生活;正常工人并不生活在我们不得不屈从的精神压力之下，没有家庭的消息，不知道他们是被送往了集中营还是直接被送进了毒气室;普通工人并不每时每刻地受到死亡的威胁。

2016-05-12 10:44:31

我的几位曾受过精神分析法训练的集中营同事经常提到集中营囚徒的“退化”—一种向更原始精神生活的倒退。囚徒的希望和梦想明显地表
现在他们的睡梦中。囚徒们经常梦见的是什么?是面包、蛋糕、香烟和舒适的热水澡。

2016-05-12 10:46:41

当最后一点皮下脂肪消失的时候，当我们看起来就像用皮肤和破布掩饰的骸镂时，我们可以看到，我们开始消耗自己的身体。生物体消耗自身的蛋白，肌肉逐渐消失了。然后，身体失去抵抗力。一个接一个地，我们栩屋仅剩的一些人开始死去。我们每个人都能相当精确地计算出下一次将轮到谁，他自己的死亡将在什么时候发生。多次观察之后，我们已经十分熟悉这些症状，并使得我们对于症状的判断具有相当的把握。

2016-05-12 10:48:04

正如前文所提到的，每当囚徒获得一点空余时间时，他们就会不可避免地想到食物。这也许可以理解为，那些没有相同经历的人几乎无法想象，濒临饿死的人所经历的毁灭灵魂的思想斗争和意志力的冲突。他们几乎无法理解这一切都将意味着什么:在壕沟里站着挖土，盼望着上午九点半或十点—半小时的午餐时间—的哨音，因为这时将分配面包(如果仍然能够供应的话);一遍又一遍地询问工头—如果他不是令人不悦的话—现在是几点钟;温存地抚摸上衣口袋中的面包，首先，用冻僵的手抚摸它，然后，籍下一点，将它放人u中，最后，用最后的一点意志力把它再次塞人口袋，暗暗发暂一定要坚持到下午。

2016-05-12 13:28:11

我的意识还停留在我的妻子的印象上。一种想法出现在我的脑海:我甚至不知道她是否还活着。我只知道一件事—至今仍记得它:爱远远超越被爱者的肉体存在。在他的精神存在和内心自我中，可以发现最深刻的意义。至于它是否实际存在。是否还活着，都不再重要。

2016-05-12 13:30:47

在黎明的灰色光线中，雪也是灰蒙蒙的;囚徒所穿的破烂衣服也是灰蒙蒙的，他们的脸也是灰蒙蒙的。我再一次默默地与妻子对话，或许可能正在努力为我的受苦受难、为我的慢慢死去寻找理由。在对即将来临死亡的绝望作最后的激烈抗争时，我意识到，我的精神正穿透四周的黑暗。我感觉到，它超越了绝望的、无意义的世界，并且，从某个地方我听见了一声胜利的“是”，来回答我的最终目是否存在的间题。在那一时刻，在巴伐利亚黎明的凄惨灰色中，一丝灯光出现在遥远的农家房屋中，它就像画在那里一样出现在地平线上。长时间地，我一动不动地站在结冰的地面上。看守走过来，侮辱我、我继续与我的爱人交谈。我越来越感觉到，她是存在的，她跟我在一起;我有一种感觉，可以摸到她，伸手就能抓住她。这一感觉十分强烈:她就在那里。那时，正是在那一时刻，一只鸟飞下来，停在我的面前，站在我从沟中挖出的土堆上，并坚定地看着我。

2016-05-12 13:33:33

对于一个局外人来说，当他发现集中营存在着某些类似于艺术的东西时，他会感到惊奇，然而，当他听说人们在那里还能找到某种幽默时，他也许会更加感到惊奇了;当然，这种幽默只有微弱的痕迹，而且，只会持续几秒和几分钟。

2016-05-12 13:33:57

在自我保护的斗争中，幽默是另外一种灵魂武器。众所周知，与人的构成中的其他任何东西相比，幽默在使人远离和超越环境方面的能力更强大，即使它只能维持几秒钟。我曾经努力培养一位在我旁边干活的朋友养成幽默感。我向他提议，我们每天至少编造一个有关我们获得解放之后的某一天可能发生的事情的故事。

继续阅读《追寻生命的意义》读书笔记