枚举

奥赛题

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++;//当一个点扩展结束后，继续后移
}