DFS

http://codeforces.com/contest/510/problem/B 题意：给定一个maze，用不同的字母代表不同的颜色。问能否找到一个颜色相同的环（失少四个点组成） 思路：dfs一遍，如果遇到之前已经访问过的点，说明成环。需要注意的是，要注意由一个点向某方向移动，然后由反方向移动到该点所造成的误判。所以dfs除了要知道当前的坐标x,y，还要记录之前的坐标px,py.

http://codeforces.com/contest/277/problem/A 题意：有n个人，每个人会一定数目的语言（可能为0），一个人学一门语言的代价为1，人和人之间沟通可以通过任意个中间人翻译。问最少的代价使得这n个人可以相互沟通。 思路：建图方式如下：第i个人会语言j，那么连上i和j+n。然后跑一遍dfs，使得1..n这n个点都被访问过。

http://codeforces.com/problemset/problem/217/A 题意：有n个雪漂（那是啥？，从某个雪漂出发走直线，只有到达另一个雪飘才能停下来。问最少需要添加多少个雪漂，才能使得可以到达任何一个雪漂。 思路：横坐标相同或者纵坐标相同的两个点之间是可以到达的。先O(N2)扫一遍建图。记录这个森林中数的个数为cnt,cnt-1即为答案。因为对于任意两个不能相互到达的点。我们只需要再来一个雪漂就可以使得这两个点相互到达。

http://codeforces.com/contest/445/problem/B 题意：一共有n种化学药品。m对关系，每对关系表示为x,y表示x和y相互反应。初始容器的danger值为1，当向容器中加入一个化学药品A，如果容器中存在化学药品和A反应，那么容器的danger值翻倍。否则不变。问一个最优的放置药品的顺序。

http://codeforces.com/problemset/problem/522/A 题意：给定某条消息的传播路径。问最远传播的距离。。 思路：其实就是问树的深度。。直接dfs就行了。。 存的时候用map<string,vector > mp；的方式存即可。

http://codeforces.com/contest/377/problem/A 题意：给定一个n*m的maze. ‘.’代表空，‘#’代表墙。要求构造一种方案，使得将k个空格填成墙壁后不影响当前的连通性（即没有被填充的空格之间可以相互到达） 思路：一开始想从上往下从左往右构造。错误的认为四个角一定是可以变成墙的。

http://codeforces.com/contest/580/problem/C 题意：给出一棵树。每个叶子节点上有一个饭店。某些节点上有cat.现在问从根节点出发可以到达多少个饭店，保证在到达饭店的路径中补连续遇到m个以上的cat. 思路：建图，然后dfs..判断为叶子节点（饭店）的方法是某个点的叶子节点数为0.

http://codeforces.com/problemset/problem/115/A 题意：给出n个人之间的上级下级关系。问如何分得最少的组，使得没一组中的人不存在上下级关系。 思路：用树的观点来考虑会很容易。可以看成给了一棵森冷。对于不同的树的相同层的点，不存在上下级关系，可以放在一个group.对于同一棵树，每一层要单独放一个group.所以答案是所有树的深度的最大值。

http://codeforces.com/contest/598/problem/D 题意：给第一个地图。 ‘.’是能走的，‘’是不能走的。**每个‘.’和’‘之间有一幅画，**给出k个起点，问对于每组起点，最多能观察到多少副画。

基础的搜索BFS和DFS，自己找题切吧… 高级搜索的题集就在下面，自己看着办吧… 努力爆搜，努力剪枝吧~~~ 【Level 1】

＿＿＿＿＿＿ 好蠢，竟然没看出来这道题的不同之处，以为就是个搜 然后样例什么的都过了… 结果显然 WA… 然后才发现，这道题应该是 tsp 问题。 解法是先跑一遍 bfs， 对于所有的脏点和起点，得到每两个点之间的距离。

dfs 1A 代码实现 1/************************************************************************* 2 > File Name: code/whust/#9/K.cpp 3 > Author: 111qqz 4 > Email: rkz2013@126.com 5 > Created Time: 2015年08月05日 星期三 15时02分30秒 6 ************************************************************************/ 7 8#include<iostream> 9#include<iomanip> 10#include<cstdio> 11#include<algorithm> 12#include<cmath> 13#include<cstring> 14#include<string> 15#include<map> 16#include<set> 17#include<queue> 18#include<vector> 19#include<stack> 20#define y0 abc111qqz 21#define y1 hust111qqz 22#define yn hez111qqz 23#define j1 cute111qqz 24#define tm crazy111qqz 25#define lr dying111qqz 26using namespace std; 27#define REP(i, n) for (int i=0;i<int(n);++i) 28typedef long long LL; 29typedef unsigned long long ULL; 30const int inf = 0x7fffffff; 31int n ,m,ans; 32int d[50]; 33int on[50],off[50]; 34int u[50],v[50]; 35 36bool ok(int x,int y) 37{ 38 if ( !d[x] && !d[y] && on[x] == off[x] && on[y] == off[y] ) 39 return true; 40 if ( !d[x] && d[y] && on[x] == off[x] ) 41 return true; 42 if ( d[x] && !d[y] && on[y] == off[y] ) 43 return true; 44 if ( d[x] && d[y] ) 45 return true; 46 return false; 47} 48 49void dfs ( int i) 50{ 51 if (i==m) 52 { 53 ans++; 54 return; 55 } 56 int x = u[i]; 57 int y = v[i]; 58 d[x]--; 59 d[y]--; 60 on[x]++; 61 on[y]++; 62 if (ok(x,y)) 63 dfs (i+1); 64 on[x]--;on[y]--; 65 off[y]++;off[x]++; 66 if ( ok( x,y)) 67 dfs (i+1); 68 off[y]--; 69 off[x]--; 70 d[x]++; 71 d[y]++; 72} 73 74int main ( ) 75{ 76 int T; 77 cin>>T; 78 while ( T-- ) 79 { 80 ans = 0; 81 scanf ("%d %d",&n,&m); 82 memset (d,0,sizeof(d)); 83 memset (on,0,sizeof(on)); 84 memset (off,0,sizeof(off)); 85 for ( int i = 0 ; i < m ; i++ ) 86 { 87 scanf ("%d%d",&u[i],&v[i]); 88 d[u[i]]++; 89 d[v[i]]++; 90 } 91 dfs (0); 92 printf ( "%d\n" , ans ); 93 } 94}

“… so forward this to ten other people, to prove that you believe the emperor has 题意是说发短信，每个人只会给一个人发，问从哪个人开始发，能传到的人最多 思路是每个人开始做一遍dfs… 毫无意外的TLE了 一个容易想到的剪枝是，如果在第i次之前的路径上的点，在之后以它作为起点遍历一定不优.

Oil Deposits # **Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 17683 Accepted Submission(s): 10172 ** Problem Description The GeoSurvComp geologic survey company is responsible for detecting underground oil deposits. GeoSurvComp works with one large rectangular region of land at a time, and creates a grid that divides the land into numerous square plots. It then analyzes each plot separately, using sensing equipment to determine whether or not the plot contains oil. A plot containing oil is called a pocket. If two pockets are adjacent, then they are part of the same oil deposit. Oil deposits can be quite large and may contain numerous pockets. Your job is to determine how many different oil deposits are contained in a grid.

http://poj.org/problem?id=1564 dfs 三个参数 x,sum,k, x表示开始的坐标，sum表示当前的和，k表示这是一组答案中的第几个数，是用来记录路径的… 调了好久没写出来…我写完之后答案会有重复.一开始想开一个boolean数组记录，这样第一组样例的3+1就只会输出一遍，但是这样，2+2就不会被记录到答案中了.