原题链接： [http://acm.hdu.edu.cn/showproblem.php?pid=1116](http://acm.hdu.edu.cn/showproblem.php?pid=1116) **一：原题内容** Problem Description Some of the secret doors contain a very interesting word puzzle. The team of archaeologists has to solve it to open that doors. Because there is no other way to open the doors, the puzzle is very important for us.  There is a large number of magnetic plates on every door. Every plate has one word written on it. The plates must be arranged into a sequence in such a way that every word begins with the same letter as the previous word ends. For example, the word acm can be followed by the word motorola. Your task is to write a computer program that will read the list of words and determine whether it is possible to arrange all of the plates in a sequence (according to the given rule) and consequently to open the door.  Input The input consists of T test cases. The number of them (T) is given on the first line of the input file. Each test case begins with a line containing a single integer number Nthat indicates the number of plates (1 <= N <= 100000). Then exactly Nlines follow, each containing a single word. Each word contains at least two and at most 1000 lowercase characters, that means only letters 'a' through 'z' will appear in the word. The same word may appear several times in the list.  Output Your program has to determine whether it is possible to arrange all the plates in a sequence such that the first letter of each word is equal to the last letter of the previous word. All the plates from the list must be used, each exactly once. The words mentioned several times must be used that number of times.  If there exists such an ordering of plates, your program should print the sentence "Ordering is possible.". Otherwise, output the sentence "The door cannot be opened.".  Sample Input ~~~ 3 2 acm ibm 3 acm malform mouse 2 ok ok ~~~ Sample Output ~~~ The door cannot be opened. Ordering is possible. The door cannot be opened. ~~~ **二：分析理解** 题目大意：给你一些英文单词，判断所有单词能不能连成一串，类似成语接龙的意思。但是如果有多个重复的单词时，也必须满足这样的条件才能算YES。否则都是不可能的情况。 解题思路：欧拉路的基本题。只要知道就可以做出来了。 关于欧拉回路和欧拉路径 定义： 欧拉回路：每条边恰好只走一次，并能回到出发点的路径 欧拉路径：经过每一条边一次，但是不要求回到起始点 ①首先看欧拉回路存在性的判定： 一、无向图 每个顶点的度数都是偶数，则存在欧拉回路。 二、有向图（所有边都是单向的） 每个节顶点的入度都等于出度，则存在欧拉回路。  三.混合图欧拉回路 混合图欧拉回路用的是网络流。 把该图的无向边随便定向，计算每个点的入度和出度。如果有某个点出入度之差为奇数，那么肯定不存在欧拉回路。因为欧拉回路要求每点入度 = 出度，也就是总度数为偶数，存在奇数度点必不能有欧拉回路。 好了，现在每个点入度和出度之差均为偶数。那么将这个偶数除以2，得x。也就是说，对于每一个点，只要将x条边改变方向（入>出就是变入，出>入就是变出），就能保证出 = 入。如果每个点都是出 = 入，那么很明显，该图就存在欧拉回路。 现在的问题就变成了：我该改变哪些边，可以让每个点出 = 入？构造网络流模型。首先，有向边是不能改变方向的，要之无用，删。一开始不是把无向边定向了吗？定的是什么向，就把网络构建成什么样，边长容量上限1。另新建s和t。对于入 > 出的点u，连接边(u, t)、容量为x，对于出 > 入的点v，连接边(s, v)，容量为x（注意对不同的点x不同）。之后，察看是否有满流的分配。有就是能有欧拉回路，没有就是没有。欧拉回路是哪个？查看流值分配，将所有流量非 0（上限是1，流值不是0就是1）的边反向，就能得到每点入度 = 出度的欧拉图。 由于是满流，所以每个入 > 出的点，都有x条边进来，将这些进来的边反向，OK，入 = 出了。对于出 > 入的点亦然。那么，没和s、t连接的点怎么办？和s连接的条件是出 > 入，和t连接的条件是入 > 出，那么这个既没和s也没和t连接的点，自然早在开始就已经满足入 = 出了。那么在网络流过程中，这些点属于“中间点”。我们知道中间点流量不允许有累积的，这样，进去多少就出来多少，反向之后，自然仍保持平衡。 所以，就这样，混合图欧拉回路问题，解了。 ②.欧拉路径存在性的判定 一。无向图 一个无向图存在欧拉路径，当且仅当   该图所有顶点的度数为偶数   或者  除了两个度数为奇数外其余的全是偶数。 二。有向图 一个有向图存在欧拉路径，当且仅当 该图所有顶点的度数为零     或者 一个顶点的度数为1，另一个度数为-1，其他顶点的度数为0。 三。混合图欧拉路径 其实整篇文章只有这部分是我写的哈，灰常不好意思，只是网上的同志们写的太好了，实在没有必要重复劳动，不知道大家有没有发现，求欧拉路径的第一步一定是求欧拉回路，在混合图上也不例外，如何判断混合图欧拉回路问题的存在性呢？首先，我们用上文所说的方法判断该图是否存在欧拉回路，如果存在，欧拉路径一定存在。如果欧拉回路不存在，那么我们枚举欧拉路径的起点和终点，连接一条无向边，然后再用最大流判断是否存在欧拉回路即可。 所以这道题的大题思路就是： 1.并查集判断连通 2.将每个单词取出首字母和尾字母，转换为一条边，然后加入对应的连通分量中。如果这个字母出现过，visit数组标记为true。同时起点出度加1，终点入度加1. 3.判断一下： 1）这个图必须是连通的，即根结点只有一个。如果不是，直接结束本次算法。 2）如果这个图是连通的，判断每个结点的入度和出度情况。 如果这个图是欧拉路，则每个顶点的出度等于入度。即out[i] = in[i] 如果这个图是半欧拉图，则起点的出度比入度大1，终点的入度比出度大1.其余顶点的出度等于入度。 如果满足上述条件，就可以将所有单词链接起来，否则不能。 当然，在判断出度入度的时候还有一点需要注意，那就是除了起点终点以外的顶点，出度必须等于入度（出度入度可以同时为2，即环），但是起点和终点必须保证出度和入度之差为1。 **三：AC代码** ~~~ #define _CRT_SECURE_NO_DEPRECATE #define _CRT_SECURE_CPP_OVERLOAD_STANDARD_NAMES 1 #include #include using namespace std; char ch[1001]; //存储单词 int pre[27]; //一共26个英文字母，下标从1开始，用于并查集 int in[27]; //表示每个单词的尾部字母的入度，默认是0 int out[27]; //表示每个单词的头部字母的出度，默认是0 bool visited[27]; //字母是否出现，默认是false int T; //测试实例个数 int N; //每个实例要输入的单词的个数 int inNum; //判断出现的所有的字母,“入度减出度为1”的个数 int outNum; //判断出现的所有的字母,“出度减入度为1”的个数 int root; //根节点个数 bool flag; //判断出现的所有的字母的出度和入度之差是否是0或1，如果不是，那肯定不满足题意,还有判断root是否大于1，大于1的话，肯定不满足 int start; int last; int Find(int x) { return (x != pre[x]) ? Find(pre[x]) : x; } void Union(int x, int y) { int root_x = Find(x); int root_y = Find(y); if (root_x != root_y) pre[root_x] = root_y; } int main() { cin >> T; while (T--) { for (int i = 1; i < 27; i++) pre[i] = i; memset(in, 0, sizeof(in)); memset(out, 0, sizeof(out)); memset(visited, 0, sizeof(visited)); inNum = outNum = root = 0; flag = true; cin >> N; for (int i = 0; i < N; i++) { cin >> ch; int len = strlen(ch); start = ch[0] - 'a' + 1; last = ch[len - 1] - 'a' + 1; visited[start] = true; visited[last] = true; out[start]++; in[last]++; Union(start, last); } for (int i = 1; i <= 26; i++) { if (visited[i]) { if (pre[i] == i) root++; if (out[i] != in[i])//注意点 { if (out[i] - in[i] == 1) outNum++; else if (in[i] - out[i] == 1) inNum++; else flag = false; } } if (!flag) break; if (root > 1) { flag = false; break; } } if ((flag&&inNum == 0 && outNum == 0) || (flag&&inNum == 1 && outNum == 1)) cout << "Ordering is possible.\n"; else cout << "The door cannot be opened.\n"; } return 0; } ~~~ 参考 ：[http://www.acmerblog.com/hdu-1116-play-on-words-1412.html](http://www.acmerblog.com/hdu-1116-play-on-words-1412.html)

原题链接： [http://acm.hdu.edu.cn/showproblem.php?pid=1518](http://acm.hdu.edu.cn/showproblem.php?pid=1518) **一：原题内容** Problem Description Given a set of sticks of various lengths, is it possible to join them end-to-end to form a square? Input The first line of input contains N, the number of test cases. Each test case begins with an integer 4 <= M <= 20, the number of sticks. M integers follow; each gives the length of a stick - an integer between 1 and 10,000. Output For each case, output a line containing "yes" if is is possible to form a square; otherwise output "no". Sample Input ~~~ 3 4 1 1 1 1 5 10 20 30 40 50 8 1 7 2 6 4 4 3 5 ~~~ Sample Output ~~~ yes no yes ~~~ **二：理解分析** 给定一堆棍子，问是否能构造出一个正方形，当然所有棍子都要使用。首先判断所有棍子长度是否能整除4，不能的话，肯定不是正方形，其次棍子中最长的那根，是否大于正方形的边长呢？大于的话，当然也是不能组成正方形的。 **三：AC代码** ~~~ #define _CRT_SECURE_NO_DEPRECATE #define _CRT_SECURE_CPP_OVERLOAD_STANDARD_NAMES 1 #include #include #include using namespace std; bool visit[21]; int square[21]; int N; int M; int sum; //周长长度 int len; //边长长度 bool flag; //标记是否已找到正方形 void DFS(int, int, int); int main() { scanf("%d", &N); while (N--) { scanf("%d", &M); memset(visit, 0, sizeof(visit)); sum = 0; flag = false; for (int i = 0; i < M; i++) { scanf("%d", &square[i]); sum += square[i]; } sort(square, square + M);//排序 len = sum / 4;//求出边长 if (sum % 4 == 0 && square[M - 1] <= len)//周长能整除4且所给长度的最大值小于等于边长才有可能构造出正方形 DFS(0, M - 1, 0); if (flag) printf("yes\n"); else printf("no\n"); } return 0; } void DFS(int sideLen, int k, int number)//sideLen代表当前正在构造的边长长度；number标记当前已经有多少条边构造出来了，当有三条边已构造出来，那么根据正方形的性质，说明此时这些棍子是可以组成正方形的 { if (sideLen == len)//已成功构造出一条边长 { number++;//这个地方起初是设置为全局变量（也就是DFS函数的第三参数起初是没有的），但是交上去WA了，最后才发现是这里错了。 sideLen = 0; k = M - 1; } if (number == 3)//正方形已构造出 { flag = 1; return; } if (flag) return; for (int i = k; i >= 0; i--) { if (!visit[i] && square[i] + sideLen <= len)//如果这根棍子没有使用过并且当前正在构造的边长加上这个棍子的总长度也是不大于边长的，那就可以了 { visit[i] = 1; DFS(sideLen + square[i], i - 1, number); if (flag) return; visit[i] = 0; while (square[i - 1] == square[i]) i--; if (len - sideLen == square[i]) return; if (sideLen == 0) return; } } } ~~~ 参考链接： [http://www.acmerblog.com/hdu-1518-Square-2075.html](http://www.acmerblog.com/hdu-1518-Square-2075.html)

原题链接：[http://acm.hdu.edu.cn/showproblem.php?pid=2614](http://acm.hdu.edu.cn/showproblem.php?pid=2614) **一：原题内容** Problem Description Zty is a man that always full of enthusiasm. He wants to solve every kind of difficulty ACM problem in the world. And he has a habit that he does not like to solve a problem that is easy than problem he had solved. Now yifenfei give him n difficulty problems, and tell him their relative time to solve it after solving the other one. You should help zty to find a order of solving problems to solve more difficulty problem.  You may sure zty first solve the problem 0 by costing 0 minute. Zty always choose cost more or equal time’s problem to solve.  Input The input contains multiple test cases. Each test case include, first one integer n ( 2< n < 15).express the number of problem. Than n lines, each line include n integer Tij ( 0<=Tij<10), the i’s row and j’s col integer Tij express after solving the problem i, will cost Tij minute to solve the problem j. Output For each test case output the maximum number of problem zty can solved. Sample Input ~~~ 3 0 0 0 1 0 1 1 0 0 3 0 2 2 1 0 1 1 1 0 5 0 1 2 3 1 0 0 2 3 1 0 0 0 3 1 0 0 0 0 2 0 0 0 0 0 ~~~ Sample Output ~~~ 3 2 4 Hint Hint: sample one, as we know zty always solve problem 0 by costing 0 minute. So after solving problem 0, he can choose problem 1 and problem 2, because T01 >=0 and T02>=0. But if zty chooses to solve problem 1, he can not solve problem 2, because T12 < T01. So zty can choose solve the problem 2 second, than solve the problem 1. ~~~ **二：理解分析** 一个人做n道题，但是他有一个习惯，每做一题，该题必须比上一次做的题的难度大，难度大小根据做题所需的时间判断。 **三：AC代码** ~~~ #define _CRT_SECURE_NO_DEPRECATE #define _CRT_SECURE_CPP_OVERLOAD_STANDARD_NAMES 1 #include #include #define max(a, b) (((a) > (b)) ? (a) : (b)) using namespace std; bool visit[16]; //从0到n-1标记题号是否做过 int time[16][16]; // int n; // int sum; //记录做出题的最大数 void DFS(int, int, int); int main() { while (cin >> n) { memset(visit, 0, sizeof(visit)); sum = 0; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cin >> time[i][j]; DFS(0, 0, 1);//第二个参数只要不大于0就行，也就是小于等于0皆可 visit[0] = 1;//解决第一题 cout << sum << endl; } return 0; } void DFS(int cur,int lastTime,int cnt)//cur代表现在正要解决的题号（从0到n-1），也就是time数组的横坐标；lastTime是上一次做题的时间；cnt是已经解决了多少题 { sum = max(sum, cnt);//这里要随时更新，因为题意是找到所能做出的题目的最大值 if (sum == n)//如果能把所有题目做完，那还做什么呢？停止！ return; for (int i = 1; i < n; i++)//第一题已被解决，所以从1开始 { if (!visit[i] && time[cur][i] >= lastTime) { visit[i] = 1; DFS(i, time[cur][i], cnt+1); visit[i] = 0; } } } ~~~

原题链接： [http://acm.hdu.edu.cn/showproblem.php?pid=1426](http://acm.hdu.edu.cn/showproblem.php?pid=1426) **一：原题内容** Problem Description 自从2006年3月10日至11日的首届数独世界锦标赛以后，数独这项游戏越来越受到人们的喜爱和重视。 据说，在2008北京奥运会上，会将数独列为一个单独的项目进行比赛，冠军将有可能获得的一份巨大的奖品———HDU免费七日游外加lcy亲笔签名以及同hdu acm team合影留念的机会。 所以全球人民前仆后继，为了奖品日夜训练茶饭不思。当然也包括初学者linle，不过他太笨了又没有多少耐性，只能做做最最基本的数独题，不过他还是想得到那些奖品，你能帮帮他吗？你只要把答案告诉他就可以，不用教他是怎么做的。 数独游戏的规则是这样的：在一个9x9的方格中，你需要把数字1-9填写到空格当中，并且使方格的每一行和每一列中都包含1-9这九个数字。同时还要保证，空格中用粗线划分成9个3x3的方格也同时包含1-9这九个数字。比如有这样一个题，大家可以仔细观察一下，在这里面每行、每列，以及每个3x3的方格都包含1-9这九个数字。 例题：  答案：  Input 本题包含多组测试，每组之间由一个空行隔开。每组测试会给你一个 9*9 的矩阵，同一行相邻的两个元素用一个空格分开。其中1-9代表该位置的已经填好的数，问号（?）表示需要你填的数。 Output 对于每组测试，请输出它的解，同一行相邻的两个数用一个空格分开。两组解之间要一个空行。 对于每组测试数据保证它有且只有一个解。 Sample Input ~~~ 7 1 2 ? 6 ? 3 5 8 ? 6 5 2 ? 7 1 ? 4 ? ? 8 5 1 3 6 7 2 9 2 4 ? 5 6 ? 3 7 5 ? 6 ? ? ? 2 4 1 1 ? 3 7 2 ? 9 ? 5 ? ? 1 9 7 5 4 8 6 6 ? 7 8 3 ? 5 1 9 8 5 9 ? 4 ? ? 2 3 ~~~ Sample Output ~~~ 7 1 2 4 6 9 3 5 8 3 6 5 2 8 7 1 9 4 4 9 8 5 1 3 6 7 2 9 2 4 1 5 6 8 3 7 5 7 6 3 9 8 2 4 1 1 8 3 7 2 4 9 6 5 2 3 1 9 7 5 4 8 6 6 4 7 8 3 2 5 1 9 8 5 9 6 4 1 7 2 3 ~~~ **二：分析理解** 先将需要填的数的坐标记录在结构体数组中，运用深搜填数，然后在通过一个judge函数判断是否符合要求 **三：AC代码** ~~~ #define _CRT_SECURE_NO_DEPRECATE #define _CRT_SECURE_CPP_OVERLOAD_STANDARD_NAMES 1 #include #include using namespace std; int map[9][9]; //存储数独 char ch; //输入数独数字和字符'？' int num; //记录有多少个'?' int p = 0; //"同一行相邻的两个数用一个空格分开"根据题意，设置个变量记录是否输出空行 bool flag; //记录是否已找到满足题意的数独 struct Node //记录'?'的横纵坐标 { int x; int y; }node[81]; void DFS(int number); int main() { while (cin>>ch) { flag = false; num = 0; if (ch == '?') { map[0][0] = 0; node[num].x = 0; node[num].y = 0; num++; } else map[0][0] = ch - '0'; for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { if (i + j == 0) continue;// cin >> ch; if (ch == '?') { map[i][j] = 0; node[num].x = i; node[num].y = j; num++; } else map[i][j] = ch - '0'; } } if (p) cout << endl; p++; DFS(0); } return 0; } bool Judge(int t, int number) { //同行同列是否有相同 for (int i = 0; i < 9; i++) { if (t == map[node[number].x][i] || t == map[i][node[number].y]) return 0; } //同一3*3方格里的数字是否重复 int x = node[number].x - node[number].x % 3; int y = node[number].y - node[number].y % 3; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { if (map[x + i][y + j] == t) return 0; } } //满足要求的话，返回1 return 1; } void DFS(int number) { if (number == num)//已找到满足要求的数独，可以输出 { flag = true; for (int i = 0; i < 9; i++) { cout << map[i][0]; for (int j = 1; j < 9; j++) cout << " " << map[i][j]; cout << endl; } return; } for (int i = 1; i <= 9; i++) { if (!flag && Judge(i, number)) { map[node[number].x][node[number].y] = i; DFS(number + 1); map[node[number].x][node[number].y] = 0; } } } ~~~ 参考： [http://www.acmerblog.com/hdu-1426-Sudoku-Killer-1896.html](http://www.acmerblog.com/hdu-1426-Sudoku-Killer-1896.html)

原题链接：[http://acm.hdu.edu.cn/showproblem.php?pid=1501](http://acm.hdu.edu.cn/showproblem.php?pid=1501) **一：原题内容** Problem Description Given three strings, you are to determine whether the third string can be formed by combining the characters in the first two strings. The first two strings can be mixed arbitrarily, but each must stay in its original order. For example, consider forming "tcraete" from "cat" and "tree": String A: cat String B: tree String C: tcraete As you can see, we can form the third string by alternating characters from the two strings. As a second example, consider forming "catrtee" from "cat" and "tree": String A: cat String B: tree String C: catrtee Finally, notice that it is impossible to form "cttaree" from "cat" and "tree". Input The first line of input contains a single positive integer from 1 through 1000. It represents the number of data sets to follow. The processing for each data set is identical. The data sets appear on the following lines, one data set per line. For each data set, the line of input consists of three strings, separated by a single space. All strings are composed of upper and lower case letters only. The length of the third string is always the sum of the lengths of the first two strings. The first two strings will have lengths between 1 and 200 characters, inclusive. Output For each data set, print: Data set n: yes if the third string can be formed from the first two, or Data set n: no if it cannot. Of course n should be replaced by the data set number. See the sample output below for an example. Sample Input ~~~ 3 cat tree tcraete cat tree catrtee cat tree cttaree ~~~ Sample Output ~~~ Data set 1: yes Data set 2: yes Data set 3: no ~~~ **二：分析理解** 参考自 [http://www.acmerblog.com/hdu-1501-Zipper-2058.html](http://www.acmerblog.com/hdu-1501-Zipper-2058.html)  。 最优子结构分析：如上例，如果A、B可以组成C，那么，C最后一个字母e，必定是 A 或 C 的最后一个字母组成。C去除除最后一位，就变成是否可以求出 A-1和B 或者 A与B-1 与 是否可以构成 C-1。。。       状态转移方程：用f[i][j] 表示 表示A前 i 为 和B 前j 位是否可以组成 C的前i+j位：dp[i][j]= (dp[i-1][j]&&(a[i]==c[i+j]))||(dp[i][j-1]&&(b[j]==c[i+j])) **三：AC代码** ~~~ #include #include using namespace std; char ch1[202], ch2[202], ch3[404]; int len1, len2, len3; int DP[202][202]; int main() { int N; cin >> N; ch1[0] = '1'; ch2[0] = '1'; ch3[0] = '1'; for (int k = 1; k <= N; k++) { cin >> ch1 + 1 >> ch2 + 1 >> ch3 + 1; memset(DP, 0, sizeof(DP)); len1 = strlen(ch1)-1; len2 = strlen(ch2)-1; len3 = strlen(ch3)-1; //处理边界 for (int i = 1; i <= len1; i++) { if (ch1[i] == ch3[i]) DP[i][0] = 1; } for (int i = 1; i <= len2; i++) { if (ch2[i] == ch3[i]) DP[0][i] = 1; } //DP for (int i = 1; i <= len1; i++) { for (int j = 1; j <= len2; j++) DP[i][j] = DP[i - 1][j] && (ch1[i] == ch3[i + j]) || DP[i][j - 1] && (ch2[j] == ch3[i + j]); } cout << "Data set " << k << ": "; if (DP[len1][len2]) cout << "yes\n"; else cout << "no\n"; } } ~~~ 　　　　　　 　　　　　  

原题链接：[http://acm.hdu.edu.cn/showproblem.php?pid=1501](http://acm.hdu.edu.cn/showproblem.php?pid=1501) **一：原题内容** Problem Description Given three strings, you are to determine whether the third string can be formed by combining the characters in the first two strings. The first two strings can be mixed arbitrarily, but each must stay in its original order. For example, consider forming "tcraete" from "cat" and "tree": String A: cat String B: tree String C: tcraete As you can see, we can form the third string by alternating characters from the two strings. As a second example, consider forming "catrtee" from "cat" and "tree": String A: cat String B: tree String C: catrtee Finally, notice that it is impossible to form "cttaree" from "cat" and "tree". Input The first line of input contains a single positive integer from 1 through 1000. It represents the number of data sets to follow. The processing for each data set is identical. The data sets appear on the following lines, one data set per line. For each data set, the line of input consists of three strings, separated by a single space. All strings are composed of upper and lower case letters only. The length of the third string is always the sum of the lengths of the first two strings. The first two strings will have lengths between 1 and 200 characters, inclusive. Output For each data set, print: Data set n: yes if the third string can be formed from the first two, or Data set n: no if it cannot. Of course n should be replaced by the data set number. See the sample output below for an example. Sample Input ~~~ 3 cat tree tcraete cat tree catrtee cat tree cttaree ~~~ Sample Output ~~~ Data set 1: yes Data set 2: yes Data set 3: no ~~~ **二：分析理解** 第三个字符串是否能由前两个字符串按照原有顺序不变的原则交叉构成。需要注意的是，visit数组元素值为1时，表示该位置已被访问过，下次无需访问。 **三：AC代码** ~~~ #define _CRT_SECURE_NO_DEPRECATE #define _CRT_SECURE_CPP_OVERLOAD_STANDARD_NAMES 1 #include #include #include using namespace std; string str1, str2, str3; int len1, len2, len3; bool flag;//为真时，表示可以输出“yes” int visit[201][201];//标记数组，默认都是0 void DFS(int i, int j, int k); int main() { int N; cin >> N; for (int i = 1; i <= N; i++) { memset(visit, 0, sizeof(visit)); flag = false; cin >> str1 >> str2 >> str3; len1 = str1.length(); len2 = str2.length(); len3 = str3.length(); DFS(0, 0, 0); if (flag) cout << "Data set " << i << ": " << "yes\n"; else cout << "Data set " << i << ": " << "no\n"; } return 0; } void DFS(int i, int j, int k) { if (flag || visit[i][j])//如果为真或该点已被访问过 return; if (k == len3)//因为根据题意len1+len2=len3 { flag = true; return; } visit[i][j] = 1; if (i < len1 && str1[i] == str3[k]) DFS(i + 1, j, k + 1); if (j < len2 && str2[j] == str3[k]) DFS(i, j + 1, k + 1); } ~~~

原题链接：[http://acm.hdu.edu.cn/showproblem.php?pid=2553](http://acm.hdu.edu.cn/showproblem.php?pid=2553) **一：原题内容** Problem Description 在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。 你的任务是，对于给定的N，求出有多少种合法的放置方法。 Input 共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。 Output 共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。 Sample Input ~~~ 1 8 5 0 ~~~ Sample Output ~~~ 1 92 10 ~~~ **二：AC代码** ~~~ #define _CRT_SECURE_NO_DEPRECATE #define _CRT_SECURE_CPP_OVERLOAD_STANDARD_NAMES 1 #include using namespace std; int a[11][11];//皇后棋盘，第一行第一列舍弃，其中第一列用来存储每一行皇后的列坐标 int b[11];//打表所用的数组 int N; int num; void DFS(int n, int & m); int main() { //////1.打表 for (int i = 1; i < 11; i++) { num = 0; DFS(1,i); b[i] = num; } //////2. while (cin >> N&&N != 0) { cout << b[N] << endl; } return 0; } bool isLegal(int & x, int & y)//判断棋盘上坐标为x，y是否可以放置皇后 { for (int i = 1; i < x; i++) { if (a[i][0] == y || abs(i - x) == abs(a[i][0] - y)) return false; } return true; } void DFS(int n,int & m)//n代表搜索到第n行，m代表是m皇后 { if (n == m+1) num++; else { for (int i = 1; i <= m; i++) { if (isLegal(n, i)) { a[n][0] = i; //a[n][i]=1; DFS(n + 1, m); } //a[n][i] = 0; } } } ~~~

原题链接：[http://acm.hdu.edu.cn/showproblem.php?pid=1072](http://acm.hdu.edu.cn/showproblem.php?pid=1072) **一：原题内容** Problem Description Ignatius had a nightmare last night. He found himself in a labyrinth with a time bomb on him. The labyrinth has an exit, Ignatius should get out of the labyrinth before the bomb explodes. The initial exploding time of the bomb is set to 6 minutes. To prevent the bomb from exploding by shake, Ignatius had to move slowly, that is to move from one area to the nearest area(that is, if Ignatius stands on (x,y) now, he could only on (x+1,y), (x-1,y), (x,y+1), or (x,y-1) in the next minute) takes him 1 minute. Some area in the labyrinth contains a Bomb-Reset-Equipment. They could reset the exploding time to 6 minutes. Given the layout of the labyrinth and Ignatius' start position, please tell Ignatius whether he could get out of the labyrinth, if he could, output the minimum time that he has to use to find the exit of the labyrinth, else output -1. Here are some rules: 1. We can assume the labyrinth is a 2 array. 2. Each minute, Ignatius could only get to one of the nearest area, and he should not walk out of the border, of course he could not walk on a wall, too. 3. If Ignatius get to the exit when the exploding time turns to 0, he can't get out of the labyrinth. 4. If Ignatius get to the area which contains Bomb-Rest-Equipment when the exploding time turns to 0, he can't use the equipment to reset the bomb. 5. A Bomb-Reset-Equipment can be used as many times as you wish, if it is needed, Ignatius can get to any areas in the labyrinth as many times as you wish. 6. The time to reset the exploding time can be ignore, in other words, if Ignatius get to an area which contain Bomb-Rest-Equipment, and the exploding time is larger than 0, the exploding time would be reset to 6. Input The input contains several test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow. Each test case starts with two integers N and M(1<=N,Mm=8) which indicate the size of the labyrinth. Then N lines follow, each line contains M integers. The array indicates the layout of the labyrinth. There are five integers which indicate the different type of area in the labyrinth: 0: The area is a wall, Ignatius should not walk on it. 1: The area contains nothing, Ignatius can walk on it. 2: Ignatius' start position, Ignatius starts his escape from this position. 3: The exit of the labyrinth, Ignatius' target position. 4: The area contains a Bomb-Reset-Equipment, Ignatius can delay the exploding time by walking to these areas. Output For each test case, if Ignatius can get out of the labyrinth, you should output the minimum time he needs, else you should just output -1. Sample Input ~~~ 3 3 3 2 1 1 1 1 0 1 1 3 4 8 2 1 1 0 1 1 1 0 1 0 4 1 1 0 4 1 1 0 0 0 0 0 0 1 1 1 1 4 1 1 1 3 5 8 1 2 1 1 1 1 1 4 1 0 0 0 1 0 0 1 1 4 1 0 1 1 0 1 1 0 0 0 0 3 0 1 1 1 4 1 1 1 1 1 ~~~ Sample Output ~~~ 4 -1 13 ~~~ **二：分析理解** 其实就是一个迷宫问题，讲述的是一个人做了一个噩梦，身处迷宫险境，只有一个出口，在规定时间内走出即可，此题的新颖处在于有个炸弹时间重设点，需要读者注意。 **三：AC代码** 方法一：BFS 参考自 [http://blog.csdn.net/jw72jw/article/details/5803926](http://blog.csdn.net/jw72jw/article/details/5803926) ~~~ #define _CRT_SECURE_NO_DEPRECATE #define _CRT_SECURE_CPP_OVERLOAD_STANDARD_NAMES 1 #include #include using namespace std; struct Node { int x; int y; int step;//走过的步数 int time;//剩余的时间 }start; int maze[10][10];//迷宫 int mark[10][10];//标记走当前步后剩余的时间 int dir[4][2] = { 0,1,1,0,0,-1,-1,0 };//下右上左,逆时针四个方向 int T, N, M; void BFS(); int main() { cin >> T; while (T--) { cin >> N >> M; for (int i = 0; i < N; i++)//数据输入 { for (int j = 0; j < M; j++) { cin >> maze[i][j]; mark[i][j] = 0;//初始化为0 if (maze[i][j] == 2)//找到起点 { start.x = i; start.y = j; start.step = 0; start.time = 6; } } } BFS(); } return 0; } void BFS() { queue q; q.push(start); mark[start.x][start.y] = start.time; Node p, temp; while (!q.empty()) { p = q.front(); q.pop(); for (int i = 0; i < 4; i++) { temp = p; temp.x += dir[i][0]; temp.y += dir[i][1]; if (temp.x >= N || temp.x <= -1 || temp.y >= M || temp.y <= -1 || maze[temp.x][temp.y] == 0) continue; temp.step++; temp.time--; if (maze[temp.x][temp.y] == 3)//出口 { cout << temp.step << endl; return; } else if (maze[temp.x][temp.y] == 4)//炸弹时间重设点 { temp.time = 6; } if (temp.time >= 2 && mark[temp.x][temp.y] < temp.time)//剩余的时间大于等于2且 { mark[temp.x][temp.y] = temp.time; q.push(temp); } } } cout << "-1\n"; } ~~~ 方法二：DFS

> 原文出处：[ACM](http://blog.csdn.net/column/details/algorithm123.html) 作者：[laojiu_](http://blog.csdn.net/laojiu_) **本系列文章经作者授权在看云整理发布，未经作者允许，请勿转载！** # ACM > 收录搜索，图论，数据结构，动态规划的习题，并配详细AC代码讲解。