原题链接：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、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复