原题链接: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; }
解题思路:
注意事项:
参考代码:
0.0分
3 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复