Biggest Number （C语言代码）

解题思路:

注意事项:

参考代码:

#include<stdio.h>
#include<string.h>
#include<stdlib.h>


typedef struct Dode{
 int x;
 int y;
}node;

int n,m;
char map[31][31];
int vis[31][31];//vis和flag数组相同功能
int flag[31][31];
char a[35];//结果串
char b[35];//工作串
char c[33];//暂时结果串
int count;
int len;
int dir[4][2]={1,0,-1,0,0,1,0,-1};
node que[1000];

int judge(int x,int y)
{
    if(x<1||x>n||y<1||y>m) return 0;
    return 1;
}


int bfs(int r,int c)
{
    int i,num=0;
    memset(flag,0,sizeof(flag));
    node a,next;
    a.x=r,a.y=c;
    int head=0,tail=0;
    que[tail++]=a;
    flag[a.x][a.y]=1;
    while(head!=tail)
    {
        node now=que[head++];
        for(i=0;i<4;i++)
        {
            next.x=now.x+dir[i][0];
            next.y=now.y+dir[i][1];
            if(!judge(next.x,next.y)||flag[next.x][next.y]||vis[next.x][next.y]) continue;
            if(map[next.x][next.y]=='#') continue;
            flag[next.x][next.y]=1;
            num++;
            que[tail++]=next;
        }
    }
    return num;
}


void dfs(int x,int y,int count1)
{
    if(count1>len||count1==len&&strcmp(a,b)<=0)
    {
        strcpy(a,b);
        len=count1;
    }
    int num=bfs(x,y);//确定还有多少个数字可以入串

    int i;
    for(i=0;i<count1;i++)//答案的前count1位跟搜到的比较。
    {
        c[i]=a[i];
    }
    c[count1]=0;

    if(count1+num<len||count1+num==len&&strcmp(c,b)>0) return ;

    for(i=0;i<4;i++)
    {
        int xx=x+dir[i][0];
        int yy=y+dir[i][1];
        if(map[xx][yy]=='#') continue;
        if(!judge(xx,yy)) continue;
        if(vis[xx][yy]) continue;
        vis[xx][yy]=1;
        b[count1]=map[xx][yy];
        dfs(xx,yy,count1+1);
        vis[xx][yy]=0;

    }
    return ;
}



int main()
{
    int i,j;
    while(scanf("%d%d",&n,&m)&&n&&m)
    {
        for(i=1;i<=n;i++)
        {
           scanf("%s",map[i]+1);
        }
      memset(a,0,sizeof(a));
      memset(b,0,sizeof(b));
    len=0;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            {
               if(map[i][j]>='1'&&map[i][j]<='9')
                {
                     memset(b,0,sizeof(b));
                     memset(vis,0,sizeof(vis));
                     vis[i][j]=1;
                     b[0]=map[i][j];
                     dfs(i,j,1);
                }
            }
        puts(a);
    }
}