---恢复内容开始---
1. 深度优先搜索DFS：
例1：给定整数a0,a1….an，判断是否可以从中选出若干数，使它们的和恰好为K。
#include<stdio.h>
bool DFS ( int i, int sum ) //已从ai之前所有项中得到和sum，现对a[i]进行判断。
{ if ( i==n ) return sum==k;
if ( DFS ( i+1, sum ) ) return true;
if ( DFS ( i+1, sum+a[i] ) ) return true;
return false ; }
void main ( ) {
if ( DFS ( 0, 0 ) ) printf ( "yes\n" );
else printf ( " no\n " ) ;
}
例2.剪格子游戏
在3*3的格子中填一些数，使得左上角的数之和等于除左上角外的所有数之和。
存在多种答疑方法时请选择左上角格子数最小的情况
1 #include <stdio.h> 2 #include<string.h> 3 #include<iostream> 4 #include<algorithm> 5 using namespace std; 6 int map[20][20], vis[20][20], s, n, m; 7 int to[4][2] = { 1, 0, -1, 0, 0, 1, 0, -1 }; 8 int dfs(int x, int y, int sum) 9 { 10 if (sum == s) 11 return 1; 12 int ans = 0; 13 for (int i = 0; i < 4; i++) 14 { 15 int tx = x + to[i][0]; 16 int ty = y + to[i][1]; 17 if (tx >= 0 && tx < n&&ty >= 0 && ty < m) 18 { 19 if (!vis[tx][ty] && map[tx][ty] + sum <= s) 20 { 21 vis[tx][ty] = 1; 22 ans = dfs(tx, ty, map[tx][ty] + sum); 23 if (ans) 24 return ans + 1; 25 vis[tx][ty] = 0; 26 } 27 } 28 } 29 return 0; 30 } 31 int main() 32 { 33 int i, j; 34 int sum = 0; 35 cin >> m >> n; 36 for (i = 0; i < n; i++) 37 { 38 for ( j = 0; j < m; j++) 39 { 40 cin >> map[i][j]; 41 sum += map[i][j]; 42 } 43 44 } 45 if (sum % 2) 46 printf("0\n"); 47 else if (map[0][0] == sum / 2) 48 printf("1\n"); 49 else 50 { 51 s = sum / 2; 52 memset(vis, 0, sizeof(vis)); 53 vis[0][0] = 1; 54 printf("%d\n", dfs(0, 0, map[0][0])); 55 } 56 return 0; 57 }
2.深度优先搜索BFS：
在一个二维的格子迷宫计算最短路径
学霸的迷宫：
第一行n,m为迷宫的长宽。接下来n行，每行m个数，数之间没有间隔，为0或1的一个，0表示可以通过，1表示不可以。假设你现在已经在迷宫坐标（1，1）的地方，即左上角，迷宫出口在（m,n）。每次移动时只能向上下左右4个方向移动到另外一个可以通过的格子里，每次移动算一步。数据保证（1，1），（n,m）课通过。
1 #include <iostream> 2 #include <string.h> 3 #include <cstdio> 4 #include <queue> 5 #include <algorithm> 6 using namespace std; 7 const int N = 500 + 10; 8 char map[N][N]; 9 int n, m; 10 bool book[N][N]; 11 struct Node{ 12 int x, y, t; 13 string s; 14 }node, tmp; 15 char c[6] = "DLRU"; 16 int step[4][2] = { { 1, 0 }, { 0, -1 }, { 0, 1 }, { -1, 0 } }; //字典序顺序 下左右上 {U,D,L,R} 17 queue<Node> q; 18 int main() 19 { 20 int i, j; 21 while (cin >> n >> m){ 22 for (i = 1; i <= n; i++) 23 for (j = 1; j <= m; j++){ 24 cin >> map[i][j]; 25 book[i][j] = 0; 26 } 27 28 node.x = 1; 29 node.y = 1; 30 node.t = 0; 31 node.s = ""; 32 q.push(node); 33 while (!q.empty()){ 34 tmp = q.front(); 35 if (tmp.x == n&&tmp.y == m) 36 break; 37 q.pop(); 38 for (i = 0; i<4; i++){ 39 int a = tmp.x + step[i][0]; 40 int b = tmp.y + step[i][1]; 41 if (a<1 || a>n || b<1 || b>m || book[a][b] || map[a][b] == ‘1‘) 42 continue; 43 book[a][b] = 1; 44 node.x = a; 45 node.y = b; 46 node.t = tmp.t + 1; 47 node.s = tmp.s + c[i]; 48 q.push(node); 49 } 50 } 51 cout << tmp.t << endl; 52 cout << tmp.s << endl; 53 } 54 return 0; 55 }
3.剪枝
---恢复内容结束---
1. 深度优先搜索DFS：
例1：给定整数a0,a1….an，判断是否可以从中选出若干数，使它们的和恰好为K。
#include<stdio.h>
bool DFS ( int i, int sum ) //已从ai之前所有项中得到和sum，现对a[i]进行判断。
{ if ( i==n ) return sum==k;
if ( DFS ( i+1, sum ) ) return true;
if ( DFS ( i+1, sum+a[i] ) ) return true;
return false ; }
void main ( ) {
if ( DFS ( 0, 0 ) ) printf ( "yes\n" );
else printf ( " no\n " ) ;
}
例2.剪格子游戏
在3*3的格子中填一些数，使得左上角的数之和等于除左上角外的所有数之和。
存在多种答疑方法时请选择左上角格子数最小的情况
1 #include <stdio.h> 2 #include<string.h> 3 #include<iostream> 4 #include<algorithm> 5 using namespace std; 6 int map[20][20], vis[20][20], s, n, m; 7 int to[4][2] = { 1, 0, -1, 0, 0, 1, 0, -1 }; 8 int dfs(int x, int y, int sum) 9 { 10 if (sum == s) 11 return 1; 12 int ans = 0; 13 for (int i = 0; i < 4; i++) 14 { 15 int tx = x + to[i][0]; 16 int ty = y + to[i][1]; 17 if (tx >= 0 && tx < n&&ty >= 0 && ty < m) 18 { 19 if (!vis[tx][ty] && map[tx][ty] + sum <= s) 20 { 21 vis[tx][ty] = 1; 22 ans = dfs(tx, ty, map[tx][ty] + sum); 23 if (ans) 24 return ans + 1; 25 vis[tx][ty] = 0; 26 } 27 } 28 } 29 return 0; 30 } 31 int main() 32 { 33 int i, j; 34 int sum = 0; 35 cin >> m >> n; 36 for (i = 0; i < n; i++) 37 { 38 for ( j = 0; j < m; j++) 39 { 40 cin >> map[i][j]; 41 sum += map[i][j]; 42 } 43 44 } 45 if (sum % 2) 46 printf("0\n"); 47 else if (map[0][0] == sum / 2) 48 printf("1\n"); 49 else 50 { 51 s = sum / 2; 52 memset(vis, 0, sizeof(vis)); 53 vis[0][0] = 1; 54 printf("%d\n", dfs(0, 0, map[0][0])); 55 } 56 return 0; 57 }
2.深度优先搜索BFS：
在一个二维的格子迷宫计算最短路径
学霸的迷宫：
第一行n,m为迷宫的长宽。接下来n行，每行m个数，数之间没有间隔，为0或1的一个，0表示可以通过，1表示不可以。假设你现在已经在迷宫坐标（1，1）的地方，即左上角，迷宫出口在（m,n）。每次移动时只能向上下左右4个方向移动到另外一个可以通过的格子里，每次移动算一步。数据保证（1，1），（n,m）课通过。
1 #include <iostream> 2 #include <string.h> 3 #include <cstdio> 4 #include <queue> 5 #include <algorithm> 6 using namespace std; 7 const int N = 500 + 10; 8 char map[N][N]; 9 int n, m; 10 bool book[N][N]; 11 struct Node{ 12 int x, y, t; 13 string s; 14 }node, tmp; 15 char c[6] = "DLRU"; 16 int step[4][2] = { { 1, 0 }, { 0, -1 }, { 0, 1 }, { -1, 0 } }; //字典序顺序 下左右上 {U,D,L,R} 17 queue<Node> q; 18 int main() 19 { 20 int i, j; 21 while (cin >> n >> m){ 22 for (i = 1; i <= n; i++) 23 for (j = 1; j <= m; j++){ 24 cin >> map[i][j]; 25 book[i][j] = 0; 26 } 27 28 node.x = 1; 29 node.y = 1; 30 node.t = 0; 31 node.s = ""; 32 q.push(node); 33 while (!q.empty()){ 34 tmp = q.front(); 35 if (tmp.x == n&&tmp.y == m) 36 break; 37 q.pop(); 38 for (i = 0; i<4; i++){ 39 int a = tmp.x + step[i][0]; 40 int b = tmp.y + step[i][1]; 41 if (a<1 || a>n || b<1 || b>m || book[a][b] || map[a][b] == ‘1‘) 42 continue; 43 book[a][b] = 1; 44 node.x = a; 45 node.y = b; 46 node.t = tmp.t + 1; 47 node.s = tmp.s + c[i]; 48 q.push(node); 49 } 50 } 51 cout << tmp.t << endl; 52 cout << tmp.s << endl; 53 } 54 return 0; 55 }
3.剪枝
若已知从当前状态无论如何转移都不会存在解，则直接跳过，不再继续搜索，称为剪枝。
如：在例1的搜索过程中，只要sum超过K，则不再继续搜索。
100
例4 带分数（蓝桥杯：历届试题）
100可以表示为带分数的形势：100=3+69258/714
还可以表示为：100=82+3546/197
带分数中数字1~9分别出现且只出现一次（不包含0）。
累死这样的分数100中有11中表示法
现将这些用代码表示出来
156.#include<stdio.h>257.#include<string.h>358.#include<algorithm>459.intvisit[10];560.inta[10];661.intkind=0;762.intsum(intbegin,intend)863.{ints=0;964.for(inti=begin;i<=end;i++)1065.s=s*10+a[i];1166.returns;1267.}1368.voidcheck(inta[],intvalue)1469.{intnum=0,temp=value;1570.for(inttemp=value;temp!=0;temp=temp/10)num++;1671.for(intk=1;k<=num;k++)1772.{intleft=sum(1,k);1873.if(left>=value)return;1974.for(intj=5+k/2;j<9;j++)2075.{inttop=sum(k+1,j);2176.intdown=sum(j+1,9);2277.if(top>down&&top%down==0&&value==left+top/down)2378.kind++;2479.}2580.}2681.}2782.voiddfs(intstart,intvalue)2883.{if(start>9)2984.{check(a,value);}3085.else{3186.for(inti=1;i<=9;i++)3287.{if(!visit[i])3388.{a[start]=i;3489.visit[i]=1;3590.dfs(start+1,value);3691.visit[i]=0;}3792.}3893.}3994.}4095.intmain()4196.{intvalue;4297.memset(visit,0,sizeof(visit));4398.memset(a,0,sizeof(a));4499.scanf("%d",&value);45100.dfs(1,value);46101.printf("%d\n",kind);47102.return0;48103.}
原文：https://www.cnblogs.com/liugangjiayou/p/10473226.html