简单搜索
1.DFS
UVA 548 树
1.可以用数组方式实现二叉树，在申请结点时仍用“动态化静态”的思想，写newnode函数
2.给定二叉树的中序遍历和后序遍历，可以构造出这棵二叉树，方法是根据后序遍历找到根，然后在中序遍历中找到树根，从而找出左右子树的结点列表然后递归 构造左右子树
3.注意这里输入的模板，用stringstream会方便
#include<iostream>
#include<string>
#include<cmath>
#include<cstring>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<queue>
#include<stack>
#include<sstream>
#include<cstdio>
#define INF 0x3f3f3f3f
const int maxn = 1e6 + ;
const double PI = acos(-1.0);
typedef long long ll;
using namespace std; const int maxv = + ;
int in_order[maxv], post_order[maxv], lch[maxv], rch[maxv];
int n; bool read_list(int* a) {
string line;
if (!getline(cin, line)) return false;
stringstream ss(line);
n = ;
int x;
while (ss >> x) a[n++] = x;
return n > ;
} int build(int L1, int R1, int L2, int R2) {
if (L1 > R1) return ;
int root = post_order[R2];
int p = L1;
while (in_order[p] != root) p++;
int cnt = p - L1;
lch[root] = build(L1, p - , L2, L2 + cnt - );
rch[root] = build(p + , R1, L2 + cnt, R2 - );
return root;
} int best, best_sum; void dfs(int u, int sum) {
sum += u;
if (!lch[u] && !rch[u]) {
if (sum < best_sum || (sum == best_sum && u < best)) {
best = u;
best_sum = sum;
}
}
if (lch[u]) dfs(lch[u], sum);
if (rch[u]) dfs(rch[u], sum);
} int main() {
while (read_list(in_order)) {
read_list(post_order);
build(, n - , , n - );
best_sum = ;
dfs(post_order[n - ], );
cout << best << "\n";
}
return ;
}
2000提高组-C 单词接龙
用substr判断能否接上
#include<iostream>
#include<string>
#include<cmath>
#include<cstring>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<queue>
#include<stack>
#include<sstream>
#include<cstdio>
#define INF 0x3f3f3f3f
const int maxn = 1e6 + ;
const double PI = acos(-1.0);
typedef long long ll;
using namespace std; string s[];
int vis[];
int Max=-;
int n; void dfs(string x, int len) {
Max = max(Max, len);
for (int i = ; i <= n; i++) {
if (vis[i] == ) continue;
int l1 = x.length();
int l2 = s[i].length();
int p = ;
while (p < min(l1, l2))
if (x.substr(l1 - p) == s[i].substr(, p)) break; else p++;
if (p < min(l1, l2)) {
vis[i]++;
dfs(x.substr(,l1-p)+s[i], len + s[i].length()-p);
vis[i]--;
}
}
} int main() {
std::ios::sync_with_stdio();
cin.tie(); cin >> n;
for (int i = ; i <= n; i++) cin >> s[i];
cin >> s[];
s[] = "" + s[];
dfs(s[], s[].length());
cout << Max-;
return ;
}
回溯 N皇后问题 http://acm.hdu.edu.cn/showproblem.php?pid=2553
#include<iostream>
#include<string>
#include<cmath>
#include<cstring>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<queue>
#include<stack>
#include<sstream>
#include<cstdio>
#define INF 0x3f3f3f3f
const int maxn = 1e6 + ;
const double PI = acos(-1.0);
typedef long long ll;
using namespace std; int x[], y[]; //x[i]为第i行所在的列
int n1, ans; bool place(int k) {
for (int i = ; i < k; i++) {
if (abs(x[i] - x[k]) == abs(i - k) || x[i] == x[k]) return false;
}
return true;
} //判断位置是否可行
void dfs(int a) { //遍历到a行，共n1行
if (a > n1) ans++; //已经放了n1个皇后
else {
for (int i = ; i <= n1; i++) {
x[a] = i;
if (place(a)) dfs(a + );
}
}
} int main() {
int n;
for (int i = ; i <= ; i++) {
ans = ;
n1 = i;
dfs();
y[i] = ans;
}
while (scanf("%d", &n), n) {
printf("%d\n", y[n]);
}
return ;
}
BFS
BFS通常用队列实现，开一个vis数组标记是否访问过
如Catch That Cow http://poj.org/problem?id=3278 如果用DFS会TLE,考虑DFS
#include<iostream>
#include<string>
#include<cmath>
#include<cstring>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<queue>
#include<stack>
#include<sstream>
#include<cstdio>
#define INF 0x3f3f3f3f
const int maxn = 1e6 + ;
const double PI = acos(-1.0);
const int N = ;
typedef long long ll;
using namespace std; int n, k;
struct Node {
int x;
int step;
};
queue<Node> q;
int vis[N]; void bfs() {
int X, Step;
while (!q.empty()) {
Node Q = q.front();
q.pop();
X = Q.x;
Step = Q.step;
if (X == k) {
printf("%d", Step);
return;
}
if (X >= && (!vis[X - ])) {
Node p;
vis[X - ] = true;
p.x = X - ;
p.step = Step + ;
q.push(p);
}
if (X <= k && (!vis[X + ])) {
Node p;
vis[X + ] = true;
p.x = X + ;
p.step = Step + ;
q.push(p);
}
if (X <= k && (!vis[X * ])) {
Node p;
vis[X * ] = true;
p.x = X * ;
p.step = Step + ;
q.push(p);
}
}
} int main() {
scanf("%d%d", &n, &k);
Node NODE ;
NODE.x = n;
NODE.step = ;
q.push(NODE);
bfs();
return ;
}
回溯法一般是要找到一个（或者所有）满足约束的解（或者某种意义下的最优解），而状态空间搜索一般是要找到一个从初始状态到终止状态的路径
路径寻找问题可以归结为隐式图的遍历，它的任务是找到一条从初始状态到终止状态的最优路径，而不像回溯法那样找到一个符合某些条件的解。
八数码问题
#include<iostream>
#include<map>
#include<queue> using namespace std; queue<int>Q;
map<int,int>vis;//标记数组
map<int,int>step;//记录到这种状态的步数 int dir[][]={-,,,,,,,-};//上，右，下，左
int mat[][];
int state;//输入的初始状态
int r,c; void input()//输入数据并将矩阵转化为一个九位整数
{
int tmp=;
for(int i=;i<;i++)
for(int j=;j<;j++)
{
cin>>mat[i][j];
tmp=tmp*+mat[i][j];
}
state=tmp;
} bool can_move(int u,int d)//判断是否可以走
{
for(int i=;i>=;i--)//将整数变回矩阵才好判断
{
for(int j=;j>=;j--)
{
mat[i][j]=u%;
u/=;
if(mat[i][j]==)
{
r=i;
c=j;
}
}
}
//判断四个方向是否能走
if((d==&&r==)||(d==&&c==)||(d==&&r==)||(d==&&c==))
return ;
return ;
} int move_to(int u,int d)//返回从状态u走到的状态
{
int tmp=;
int nr=r+dir[d][];
int nc=c+dir[d][];
mat[r][c]=mat[nr][nc];
mat[nr][nc]=;
for(int i=;i<;i++)
{
for(int j=;j<;j++)
tmp=tmp*+mat[i][j];
}
return tmp;
} int bfs(int s)
{
Q.push(s);
vis[s]=;
step[s]=;
while(Q.size())
{
int u,v;
u=Q.front();
Q.pop();
if(u==)
return step[u];
for(int i=;i<;i++)
{
if(can_move(u,i))
{
v=move_to(u,i);
if(!vis[v])
{
vis[v]=;
step[v]=step[u]+;
Q.push(v);
}
}
}
}
return -;
} int main()
{
input();
int ans=bfs(state);
cout<<ans<<endl;
return ;
}
拓扑排序
不包含有向环的有向图称为有向无环图（DAG），如果图中存在有向环，则不存在拓扑排序