枚举
奥赛题炸弹人游戏用火柴棒摆出A+B=C 搜索
深度优先搜索
放牌游戏奥赛题拓展算法迷宫问题 层层递进——广度优先搜索
迷宫游戏改造
枚举 奥赛题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搜索 深度优先搜索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(stepn||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(headn||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++;//当一个点扩展结束后，继续后移
}
