DFSKEY WORD：　　盲搜    递归    遍历所有状态  栈（隐式利用）

/**1.部分和问题给定整数 a1 a2 …… an 判断是否可以从中选出若干数，使得他们的和等于kn大于等于1 小于等于20ai和k范围：-10^8 10^8此类题，拒绝暴力*/#include "cstdio"#define N 25int a[N];int n,k;///从前i项得到了和sum,然后对i项之后的进行分支bool dfs(int i,int sum){    ///n项都计算过，返回sum和k是否相等    if(i==n)return sum==k;    ///不加上a[i]    if(dfs(i+1,sum))return true;    ///加上    if(dfs(i+1,sum+a[i+1])) return true;    ///无论加不加上都不能构成    return false;}void solve(){    if(dfs(0,0))        printf("Yes\n");    else        printf("No\n");}int main(){    //freopen("in.txt","r",stdin);    //freopen("out.txt","w",stdout);    while(~scanf("%d",&n))    {        for(int i=1;i<=n;i++)            scanf("%d",&a[i]);        scanf("%d",&k);        solve();    }    return 0;}

4

1 2 4 7

13

4

1 2 4 7

15

Yes

No

积水问题：求水洼个数（8连通的积水认为连通）

#include "cstdio"#define N 100char field[N][N];int n,m;void dfs(int x,int y){    if(x<0||y<0||x>=n||y>=m)return;    if(field[x][y]=='w'){        field[x][y]='.';        for(int i=-1;i<=1;i++)        {            for(int j=-1;j<=1;j++){                int nx=x+i,ny=y+j;                dfs(nx,ny);            }        }    }    else        return;}void solve(){    int cnt=0;    for(int i=0;i

 

BFS

KEY WORD:队列 近->远遍历

容易用来求，最短路径，最少操作之类问题

key  状态   转移方式

/**1.迷宫的最短路径问题# . S G墙壁 通道 起点 终点*/#include "iostream"#include "cstdio"#include "queue"using namespace std;#define MAX 110const int INF=100000000;typedef pair
     
      P;///状态char maze[MAX][MAX];///迷宫int d[MAX][MAX];///起点到各个位置最短距离的数组int N,M;int sx,sy;///地点 坐标int gx,gy;///终点int dx[4]={
   1,0,-1,0},dy[4]={
   0,1,0,-1};int bfs(){    queue
      
 que;    ///INIT    for(int i=0;i
     

10 10

#S######.#

......#..#

.#.##.##.#

.#........

##.##.####

....#....#

.#######.#

....#.....

.####.###.

....#...G#

22