Biggest Number (错误代码时间超限制)

#include<stdio.h>
char result[50]={'\0'};
char s[50];
int len=0,a[15][15],row,col;
void strcpy(char a[],char b[])
{
    while(*(a++)=*(b++));
}
int strcmp(char a[],char b[])
{
    while(*a==*b)
    {
        if(*a=='\0') return 0;
        a++;
        b++;
    }
    if(*a>*b) return 1;
    if(*a<*b) return -1;
}
void fact(int i,int j,int x)
{
    int t=a[i][j];
    s[x]='0'+a[i][j];
    if(i-1>=0 && a[i-1][j]!=0)
    {
        a[i][j]=0;
        fact(i-1,j,x+1);
        a[i][j]=t;
    }
    if(i+1<row && a[i+1][j]!=0)
    {
        a[i][j]=0;
        fact(i+1,j,x+1);
        a[i][j]=t;
    }
    if(j-1>=0 && a[i][j-1]!=0)
    {
        a[i][j]=0;
        fact(i,j-1,x+1);
        a[i][j]=t;
    }
    if(j+1<col && a[i][j+1]!=0)
    {
            a[i][j]=0;
            fact(i,j+1,x+1);
            a[i][j]=t;
    }
    s[x+1]='\0';
    if(x<len ) return ;
    if(x>len) strcpy(result,s),len=x;
    if(x==len)
    if(strcmp(s,result)>0) strcpy(result,s);
}
int main(void)
{
    char c;
    int i , j;
    while(scanf("%d%d",&row,&col)==2)
    {
        getchar();
        if(row == col && row ==0) break;
        for(i=0;i<row;i++)
        {
              for(j=0;j<col ;j++){
              c=getchar();
              if(c=='#') a[i][j]=0;
              else a[i][j]=c-'0';  }
              getchar();
        }
        for(i=0;i<row;i++)
        {
            for(j=0;j<col;j++)
            if(a[i][j]!=0) fact(i,j,0);
        }
        printf("%s\n",result);
        result[0]='\0';
    }
    return 0;
}













#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int dr[]={0,1,0,-1};
const int dc[]={1,0,-1,0};
int row, col ;
int ok=0,ans[100],v[100],depth;
char maze[100][100];
int g[100][4];
int deg[100];
int cnt ,x[50],y[50],id[100][100],vis[100];
int inside(int r,int c){
    if(r >= 0 && r < row && c>=0 && c<col  && maze[r][c]!='#'){
        return 1;
        }
    return 0;
}
void dfs(int cur,int  front)
{
    if(cur>=depth)
    {
        ok = 1 ; //至少已经找到了一个解
                        for(int i=0;i<depth;i++)
                printf("%c",maze[x[v[i] ] ][y[v[i] ] ]);
                printf("\n");
        int i=0;
        while(maze[x[v[i] ] ][y[v[i] ] ]== maze[x[ans[i] ] ][y[ans[i] ] ] && i<depth)  i++;
        if( ans[0]==0 || maze[x[v[i] ] ][y[v[i] ] ] > maze[x[ans[i] ] ][y[ans[i] ] ] )
        memcpy(ans,v,sizeof(int)*depth);
        return ;
    }
    for(int i=0;i<deg[front];i++){
        v[cur]=g[front][i];
        if(vis[g[front][i]]) {
            continue;
        }
        else {
            vis[g[front][i]]=1;
            dfs(cur+1,g[front][i]);
            vis[g[front][i]]=0;
        }
    }
}
int main(void)
{
    while(scanf("%d%d",&row , &col) && row && col){
        scanf("\n");
        for(int i=0;i<row;i++) fgets(maze[i],20,stdin);
        memset(id,-1,sizeof(id));
        memset(g,-1,sizeof(g));
        cnt = 0 ;
        for(int i=0;i<row;i++)
        for(int j=0;j<col;j++)
        if(maze[i][j]!='#')  {
            x[cnt]=i,y[cnt]=j;
            id[i][j]=cnt ;
            cnt++;
        }
        for(int i=0;i<cnt;i++){
            int r=x[i];
            int c=y[i];
            deg[i]=0;
            for(int j=0;j<4;j++){
                if(inside(r+dr[j],c+dc[j])==1)   g[i][deg[i]++]=id[r+dr[j]][c+dc[j]];
            }
        }
        for(depth=cnt;;depth--)
        {
            ok=0;
            memset(ans,0,sizeof(ans));
            for(int i=0;i<cnt;i++){//枚举首个元素
                memset(vis,0,sizeof(vis));
                v[0]=i;
                vis[i]=1;
                dfs(1,i);
                vis[i]=0;
            }
            if(ok){//如果已经找到了
                for(int i=0;i<depth;i++)//按照深度进行输出
                printf("%c",maze[x[ans[i] ] ][y[ans[i] ] ]);
                printf("\n");
                break;
            }
        }
    }
    return  0;
}




//回溯法,对于不满足条件的分支回溯
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int row , col ,flag , maxn;
char maze[100][100];
int v[100] , ans[100] ;
int vis[100][100],vis2[100][100];
const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,0};
struct point {
    int x,y;
    point(int x=0,int y=0,int step=0):x(x),y(y){}
};
int inside(int x,int y){
    if(x>=0 && x<row && y>=0 && y<col && maze[x][y]!='#')
    return 1;
    return 0;
}
void dfs(int r,int c,int len)
{
     if( len>maxn ||( len==maxn && flag==1)){
        memcpy(ans,v,sizeof(v));
        maxn = len;
        flag = 0;
     }
    memset(vis2,0,sizeof(vis2));
    vis2[r][c]=1;
    queue<point>q;
    q.push(point(r,c));
    int maxn_leave=0;
    while(!q.empty()){
        point a=q.front(); q.pop();
        int r=a.x,c=a.y;
        for(int i=0;i<4;i++)
        if(inside(r+dx[i],c+dy[i]) && !vis[r+dx[i]][c+dy[i]] &&!vis2[r+dx[i]][c+dy[i]] ){
            vis2[r+dx[i]][c+dy[i]]=1;
            q.push(point(r+dx[i],c+dy[i]));
        }
        maxn_leave++;
    }
    if(maxn_leave-1+len < maxn || (maxn_leave+len-1==maxn && flag == -1) ) return ;
    for(int i=0;i<4;i++){
        int x=r+dx[i],y=c+dy[i];
        if(inside(x,y) && !vis[x][y]){
            v[len]=maze[x][y]-'0';
            vis[x][y]=1;
             if (flag!=0)  dfs(x,y,len+1);
            else if(len>maxn){
                flag =1;
                dfs(x,y,len+1);
                flag = 0 ;
            }
            else {
                flag = v[len] > ans[len] ? 1:(v[len]==ans[len]?0:-1);
                dfs(x,y,len+1);
                flag = 0 ;
            }
            vis[x][y]=0;
        }
    }
}
int main(void)
{
    while(1){
        scanf("%d%d",&row , &col);
        if(row==0 && col==0) break;
        for(int i=0;i<row;i++) scanf("%s",maze[i]);
        memset(v,0,sizeof(v));
        memset(vis,0,sizeof(vis));
        memset(ans,0,sizeof(ans));
        ans[0] = -1;
        maxn=1;//当前最长的数字长度为1
        for(int i=0;i<row;i++)
            for(int j=0;j<col;j++)
                if(maze[i][j]!='#'){
                    vis[i][j]=1;
                    v[0]=maze[i][j]-'0';
                    flag = (v[0] > ans[0]) ? 1 :(v[0]==ans[0]?0:-1);
                    dfs(i,j,1);
                    vis[i][j]=0;
                }
        for(int i=0;i<maxn;i++)
        printf("%d",ans[i]);
        printf("\n");
    }
    return 0;
}

解题思路:





注意事项:





参考代码: