jimore

用户名：uq_30465888842

访问量：9793

签　名：

Don't let the dream just be a dream!!!

等　　级
排　　名	177
经　　验	6849
参赛次数	29
文章发表	63
年　　龄	0
在职情况	学生
学　　校	四川农业大学
专　　业	计算机科学与技术

　　自我简介：

目标院校：上海交通大学

TA的其他文章

one-shot learning
浏览：198

二分答案（简单理解）
浏览：449

求一个很大的数的所有质因子（新方法）
浏览：247

你可能喜欢

DFS+BFS（c++题解）

　　作者: jimore　　　　发表时间：2022-07-23 20:22:44 浏览：285　|　评论：0　

原题链接：Biggest Number

## BFS+DFS

**注意DFS要多剪枝**

* 把每一个数字坐标作为起始点，对每一个起始点进行DFS
  
* 在DFS中，每走到一个坐标，就要用BFS判断后面的位数有多少，看看能不能比现在目前最大的数字的位数要多，如果多的话就继续，不然就直接剪枝。

#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];
    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++)
        {
            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);
        }
    }

0.0分

1 人评分

新上线《蓝桥杯辅导》课程，近五年的蓝桥杯省赛与国赛真题都有，从读题开始理解题意、梳理思路、实现代码再提交评测全过程，可有效提升获奖比例甚至进国赛！课程介绍、试听请猛击这里

jimore

TA的其他文章

你可能喜欢

图形输出（Java代码）

求最大公约数-模板题

简单的a+b （C语言代码）

简单的a+b （C++语言代码）

数组输出（C语言代码）--此题的题目描述有问题

DFS+BFS（c++题解）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言考试练习题_一元二次方程（C语言代码）

Hello, world! （C++代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

Tom数（C语言代码）

C二级辅导-求偶数和（C语言代码）

A+B for Input-Output Practice (I) （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

jimore

TA的其他文章

你可能喜欢

图形输出 （Java代码）

求最大公约数-模板题

简单的a+b （C语言代码）

简单的a+b （C++语言代码）

数组输出 （C语言代码）--此题的题目描述有问题

DFS+BFS（c++题解）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言考试练习题_一元二次方程 （C语言代码）

Hello, world! （C++代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

Tom数 （C语言代码）

C二级辅导-求偶数和 （C语言代码）

A+B for Input-Output Practice (I) （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

图形输出（Java代码）

数组输出（C语言代码）--此题的题目描述有问题

　　评论区

C语言考试练习题_一元二次方程（C语言代码）

Tom数（C语言代码）

C二级辅导-求偶数和（C语言代码）