枚举

奥赛题

xxx+xxx=xxx(把数字1-9插入到x中，每个数字只可使用一次使得等式成立）。请问有多少种组合可以满足这个条件？

int main()
{int a[10],i,total=0,book[10],sum=0;//a[i]代表依次出现的每一位，book[i]代表某个数出现的次数//sum为出现的不同数的数目for(a[1]=1;a[1]<=9;a[1]++）for(a[2]=1;a[2]<=9;a[2]++）for(a[3]=1;a[3]<=9;a[3]++）……{for(i=0;i<9;i++)book[i]=0;//初始化for(i=0;i<9;i++)book[a[i]]=1;//某个数字出现就标记一下for(i-1;i<=9;i++)sum+=book[i];if(sum==9&&a[1]*100+a[2]*10+a[3]+……==a[7]*100+a[8]*10+a[9])total++;}printf("%d',totai/2);}

炸弹人游戏

炸弹需要放在空地，并且炸弹不能穿墙，需要确定炸弹最多能炸死多少个怪兽？
思考：将墙，怪兽和炸弹转换到二维坐标系中，用二维数组存储，分别从上下左右四个方向探测可以消灭的敌人数

int main()
{char a[20][20];int i,j,sum,map=0,p,q,x,y,n,m;scanf("%d%d",&n,&m);//n代表每行有多少个字符，m代表每列有多少个字符//读入每行字符for(i=0;i<=n-1;i++)scanf("%s",a[i]):for(i=0;i<=n-1;i++)for(j=0;j<=m-1;j++)if(a[i][j]=".")//如果为空地{sum=0;x=i,y=j;while(a[x][y]!='#')//不是墙的时候{ if(a[x][y]=='G')sum++；x--;//向上统计}x=i,y=j;while(a[x][y]!='#')//不是墙的时候{ if(a[x][y]=='G')sum++；x++;//向下统计}x=i,y=j;while(a[x][y]!='#')//不是墙的时候{ if(a[x][y]=='G')sum++；y--;//向左统计}  x=i,y=j;while(a[x][y]!='#')//不是墙的时候{ if(a[x][y]=='G')sum++；y++;//向上统计}//更新map
if(sum>map){map=sum;p=i;//用p和q记录当前点的坐标q=j;}
}
}

用火柴棒摆出A+B=C

题目：（1）加号和等号各需要俩跟火柴棒
（2）枚举A和B,算出C可以降低复杂度
（3）如果A!=B，则A+B=C和B+A=C可以看成俩个不同的等式
（4）所有火柴必须全部用上
假设焦琪现在有m根火柴（m<=24),可以拼出多少个等式？

分析：（1）20根火柴最多组成10个1，所以可以表示的最大数字是1111

#include<stdio.h>int fun(int a)
{int num=0;int f[10]={6,2,5,5,4,5,6,3,7,6};while(a/10!=0){//至少有俩位sum+=f[a%10];x/=10;}sum+=f(a):return num;}int main()
{int a,b,c,m,sum=0;scanf("%d",&m);)for(a=0；a<=1111;a++)for(b=0;b<=1111;b++){c=a+b;if(fun(a)+fun(b)+fun(c)==20-m)sum++;}printf("%d",sum);}

搜索

深度优先搜索

关键：解决当前应该怎么做，至于下一步该怎么做和当前一步是一样的。

放牌游戏

例如：有123三张牌和123三个盒子，要把这三张牌放到三个盒子里面。

解析当我们把123放在123三个盒子里面的时候，往后走一步到第四个盒子，发现不存在。
往回走到第三个盒子，回收里面的牌之后，再到第二个盒子，回收里面的牌，可以对第二个盒子投入2或者3，依次类推，就可以得到多个组合。

void dfs(int step)
//step代表着站在第几个盒子前面
{int i;if(step==n+1){for(int i=1;i<=n;i++)printf("%d",a[i])}
// 站在第step个盒子面前，按照1，2，3，…n的方式尝试放入牌for(int i=1;i<=n;i++)if(book[i]==0){a[step]=i;book[i]=1;//表明这张牌已经不再手里了dfs(step+1):book[i]=0;//必须要把牌收回，因为如果上一次摆放结束的时候没收回牌，就无法完成下一次摆放}
}

抽象出来包含了深度优先搜索的模型：每一次的尝试都是一种扩展，每站在一个盒子面前，都有n中扩展方式，但不是每种扩展都能成功。

void dfs(int step)
{判断边界尝试每一种可能{继续下一步}返回}

奥赛题拓展算法

void dfs(int step)
{int i,a[10],book[10];if(step==10){if(a[1]*100+……==a[7]*100……)total++;printf("%d",total/2):return;}for(i=1;i<=9;i++){if(book[i]==0){a[step]=i;book[i]=1;dfs(step+1);book[i]=0;}}return;
} 

迷宫问题

要找到（1，1）到（p,q)的最短路径，这中间有障碍物，并且不能出墙。
分析：我们只能按顺时针方向一个一个点去尝试，直到走不通的时候再去尝试另一个路线。最后将所有的路线比较最小值。

void dfs(int x,int y,int step)
{int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//方向数组next判断向哪边走int tx,ty,k;//下一步的横纵坐标if(x==p&&y==q){if(step<min)min=step;return;}//枚举四种走法
for(k=0;k<=3;k++)
{tx=x+next[k][0];ty=y+next[k][1];//判断是否越界if(tx<1||tx>n||ty<1||ty>m)continue;//判断该点是否为障碍物或者在路径中if(a[tx][ty]==0&&book[tx][ty]==0){book[tx][ty]=1;dfs(tx,yt,step+1);book[tx][ty]=0;}
}
return;
}

层层递进——广度优先搜索

BFS（宽度优先搜索）

迷宫游戏改造

一层一层扩展，每扩展依次，就把发现的点加入到队列中，直到找到目标点。

struct note{int x;//横坐标int y;//纵坐标int f;//父亲在队列中的编号int step;//步数}

int main()
{struct note que[2501];int a[51][51]={0},book[51][51]={0};//定义方向数组int next[4][2]={{0,1},{1,0},{0,-1}{-1,0}};int m,n,i,j;scanf("%d%d",&n,&m);for(i=1;i<=n;i++)for(j=1;i<=m;j++)scanf("%d",&a[i][j]);//队列初始化
head=tail=1;
//插入迷宫入口坐标
que[tail].x=startx;
que[tail].y=starty;
que[tail].f=0;
que[tail].s=0;
tail++;
book[startx][starty]=1;flag=0;//flag来标记是否到达目标点while(head<tail)
{//枚举四个方向for(k=0;k<=3;k++){tx=que[head].x+next[k][0];ty=que[head].x+next[k][1];//判断是否越界if(tx<1||tx>n||ty<1||ty>m)continue;//判断该点是否为障碍物或者在路径中if(a[tx][ty]==0&&book[tx][ty]==0){book[tx][ty]=1;//插入新的点到队列中que[tail].x=tx;que[tail].y=ty;que[tail]=que[head]+1;//步数比父亲步数大一tail++;}if(tx==p&&ty==q){//找到目标点停止扩展flag=1;break;}
}
if(flag==1) break;
head++;//当一个点扩展结束后，继续后移
}