Biggest Number （C++代码）回溯法

    #include <cstdio>
    #include <cstring>
    using namespace std;

    int row,col;
    char maze[20][20];
    int vis[20][20];//判断是否走过改路径
    int ans[100];//存放当前最大数数组
    int ansl;//记录当前最大数位数
    int v[100];//当前数
    int stack[100][2];
    int used1[20][20];//这个也是判断是否走过路径 下面代码中只用在一处地方
    const int dx[]={0,1,0,-1};
    const int dy[]={1,0,-1,0};
    int z;
    void solve(int x,int y,int len)//搜索函数
    {
         int i,j,top,bottom,xx,yy;
         if ((len>ansl)||((len==ansl)&&(z==1)))//如果该数大于最大数  z用来判断大小的 注意后面用法
        {
              memcpy(ans,v,sizeof(v));//aa数组值复制到ans中去
              ansl=len;
              z=0;
         }
         memset(used1,0,sizeof(used1));//初始化use1为0  即都没使用过
         used1[x][y]=1;
         top=0;bottom=1;//下面会用栈来存放后继结点的坐标 为的是记录当前数之后能构成的最长的数
         stack[0][0]=x;
         stack[0][1]=y;
         while (top<bottom)//把后继结点都放入栈中  这里是提高速度的一核心
         {
              for (i=0;i<4;i++)//上下左右
              {
                   xx=stack[top][0]+dx[i];
                   yy=stack[top][1]+dy[i];
                   if ((xx>=0)&&(xx<row)&&(yy>=0)&&(yy<col)&&(maze[xx][yy]!='#')&&(vis[xx][yy]==0)&&(used1[xx][yy]==0))
                   {
                        stack[bottom][0]=xx;
                        stack[bottom][1]=yy;
                        used1[xx][yy]=1;
                        bottom++;
                   }
              }
            top++;
         }
         if (len+top-1<ansl) return;//如果当前长度+后继结点构成最长数长度<最大数长度 直接返回
         if ((len+top-1==ansl)&&(z==-1)) return;//长度相等但是比最长数小
             for (i=0;i<4;i++)//上下左右递归寻找下一个结点
             {
              xx=x+dx[i];
              yy=y+dy[i];
              if ((xx>=0)&&(xx<row)&&(yy>=0)&&(yy<col)&&(maze[xx][yy]!='#')&&(vis[xx][yy]==0))
              //下面都是search 注意z的值及其含义
              {
                   v[len]=maze[xx][yy]-'0';
                   vis[xx][yy]=1;
                   if (z!=0)  solve(xx,yy,len+1);
                   else if (len>=ansl)
                    {
                         z=1;
                         solve(xx,yy,len+1);
                         z=0;
                    }
                    else
                    {
                         if (v[len]>ans[len])
                         {
                              z=1;
                              solve(xx,yy,len+1);
                              z=0;
                         }
                         else if (v[len]==ans[len])
                         {
                              z=0;
                              solve(xx,yy,len+1);
                              z=0;
                         }
                         else
                         {
                              z=-1;
                              solve(xx,yy,len+1);
                              z=0;
                         }
                    }
                   vis[xx][yy]=0;
              }
         }
    }

    int main()//main里面和search里面大同小异 就是把第一个结点单独拿出来而已 接下来的结点都是遍历过程
    {
     int i,j;
     while (1)
     {
          scanf("%d%d",&row,&col);
          if ((row==0)&&(col==0)) break; //判断是否是种植条件
          for (i=0;i<row;i++)
          scanf("%s",maze[i]);//读入一行 ， 读入字符串 ， 或者使用fgets();
          memset(ans,0,sizeof(ans));  //初始化答案数组
          ans[0]=-1; //答案数组首位设置为 -1
          ansl=1;//当前最大数位数是1
          memset(v,0,sizeof(v));//数组v保存目前的数字,初始化数组
          for (i=0;i<row;i++)
           for (j=0;j<col;j++)
            if (maze[i][j]!='#')
            {
                 vis[i][j]=1;//访问了该位置的数字
                 v[0]=maze[i][j]-'0';
                 if (maze[i][j]-'0'>ans[0])
                 {
                      z=1;
                      solve(i,j,1);
                 }
                 else if (maze[i][j]-'0'==ans[0])
                 {
                      z=0;
                      solve(i,j,1);
                 }
                 else if (maze[i][j]-'0'< ans[0])
                 {
                      z=-1;
                      solve(i,j,1);
                 }
                 vis[i][j]=0;//使用了辅助的全局变量，则一定要及时的回复原状
            }
          for (i=0;i<ansl;i++)
          printf("%d",ans[i]);
          printf("\n");
     }
     return 0;
    }

解题思路:





注意事项:





参考代码: