算法学习之剪枝
从N到K的最短路径问题，显然用BFS
而对于路径问题，应该用DFS，因为DFS“一路深入”，天然就产生了一条路径，而BFS逐层推进，把层与层之间连续的路径打断了，想表示一个路径很困难。
BFS的剪枝：去重
DFS的剪枝：
- 可行性剪枝：对当前状态进行检查，如果当前条件不合法就不再继续，直接返回。
- 搜索顺序剪枝：搜索树有多个层次和分支，不同的搜索顺序会产生不同的搜索树形态，复杂度也相差很大。
- 最优性剪枝：在最优化问题的搜索过程中，如果当前花费的代价已超过前面搜索到的最优解，那么本次搜索已经没有继续进行下去的意义，此时停止对当前分支的搜索进行回溯。
- 排除等效冗余：搜索的不同分支，最后的结果是一样的，那么只搜一个分支就够了。
- 记忆化搜索：在递归的过程中，有许多分支被反复计算，会大大降低算法的执行效率。用记忆化搜索，将已经计算出来的结果保存起来，以后需要用到的时候直接取出结果，避免重复运算，从而提高了算法的效率。
==数字三角形==
链接：https://www.luogu.com.cn/problem/P1118
剪枝思想：
三角计算的优化。对排列进行三角形计算，
-并不需要按部就班地算
比如{a,b,c,d,e}这5个数，直接算最后一行的公式a+4b+6c+4d+e就好了，复杂度是O(N)的。不同的N有不同的系数，比如5个数的系数是{1,4,6,4,1}，提前算出所有N的系数备用。可以发现，==这些系数正好是杨辉三角。==最优性剪枝。==对某个排列求三角形和时，如果前面几个元素和已经大于sum，那么后面的元素就不用再算了。==
==吃奶酪==
链接：https://www.luogu.com.cn/problem/P1433
注意，本题用剪枝的话会卡最后一个测试点（最后一个测试点专门来卡搜索的，这道题正解状压DP，我只是拿这道题说一下剪枝的思想）
剪枝思想：
在DFS中，用sum记录当前最短距离，每次计算新的路径时，如果超过了sum，就退出。剪枝的效率和测试数据有关，如果碰巧有很恶劣的数据，会超时。
链接：https://vjudge.net/problem/HDU-1010#author=BlueLine
奇偶剪枝：
把地图看做一下的形式：
0 1 0 1 0 1
1 0 1 0 1 0
0 1 0 1 0 1
1 0 1 0 1 0
0 1 0 1 0 1
1 0 1 0 1 0
我们可以很容易的得出从1到1或者从0到0必然有偶数步 而从1到0则必然有奇数步 假如我们从起点到终点最短步数为x步，而我们需要的步数为T步,那么T-x的值一定为一个偶数。我们可以这么想，从起点走到某一点k，为了保证最后的步数为T，那么我们应该保证k进行一段绕路最后再回到k，那么这中间的步数一定是偶数步。
参考资料：https://www.cnblogs.com/wkfvawl/p/9337156.html
同时 如果想知道两个点的奇偶性的话，只需要计算曼哈顿距离即可。
在本题中，只需要对起点S、终点D做一次奇偶判断就够了，DFS内部不用再做。因为，从S走到方格中的任何一点x，x与D的奇偶性，与S和D的奇偶性相同。
所以，奇偶判断应该在DFS之前做，判断有解后再进行DFS。DFS内部的奇偶判断是多余的；奇偶判断并不能减少DFS内部搜索的数量，因为这是独立的两件事。
同时还有一个可行性剪枝：
当前走了k步，如果k>T，已经走的超过了限制步数，还没有找到D点，则剪掉。
代码：
#include <bits/stdc++.h>
using namespace std;
char mp[10][10];
int vis[10][10];
int a,b,x,y;
int n,m,t;
int flag=0;
int dic[4][2]={1,0,-1,0,0,1,0,-1};
void dfs(int xx,int yy,int time){
if(xx==x&&yy==y){
if(time==t)flag=1;
return ;
}
if(flag)return ;
if(time>t)return ;
vis[xx][yy]=1;
for(int i=0;i<4;i++){
int fx=xx+dic[i][0];
int fy=yy+dic[i][1];
if(fx>=0&&fx<n&&fy>=0&&fy<m&&mp[fx][fy]!='X'&&vis[fx][fy]==0){
vis[fx][fy]=1;
dfs(fx,fy,time+1);
vis[fx][fy]=0;
}
}
}
int main(){
while(scanf("%d%d%d",&n,&m,&t)){
//getchar();
if(!n&&!m&&!t)break;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>mp[i][j];
if(mp[i][j]=='S'){
a=i,b=j;
}
if(mp[i][j]=='D'){
x=i,y=j;
}
}
//getchar();
}
int T=t-abs(x-a)-abs(y-b);
//cout<<T<<endl;
if(T<0||T&1){
puts("NO");
continue;
}
memset(vis,0,sizeof(vis));
flag=0;
dfs(a,b,0);
if(flag)puts("YES");
else puts("NO");
}
}
剪枝太巧妙了..我太菜了..
各种各样题目的题解
