当前位置: 首页 > article >正文

学习总结1

算法

这两天对搜索(主要是dfs)进行了复习,写了四道题目.

解题思路

这道题我用dfs进行解题,这道题比起其他的只多了一个Z轴也就是多了两个方向.

代码

#include <string.h>
#include <stdio.h>
char g[31][31][31];
int ne[7][3]={{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};
int j[31][31][31];
struct dui
{
    int x;
    int y;
    int z;
}d[31*31*31];
int l,r;
int x,y,z;
int bfs()
{
    int tx,ty,tz,k;
    while(l<r)
    {
        for(k=0;k<6;k++)
        {
            tz=ne[k][0]+d[l].z;
            tx=ne[k][1]+d[l].x;
            ty=ne[k][2]+d[l].y;
            if(tz>z||tz<0||tx>x||tx<0||ty>y||ty<0)
                continue;
            if(g[tz][tx][ty]=='E')
            {
                return j[d[l].z][d[l].x][d[l].y]+1;
            }
            if(j[tz][tx][ty]==0&&g[tz][tx][ty]=='.')
            {
                j[tz][tx][ty]=j[d[l].z][d[l].x][d[l].y]+1;
                d[r].z=tz;
                d[r].x=tx;
                d[r++].y=ty;
            }
        }
        l++;
    }
    return 0;
}
int main()
{
    int a,b,c;
    while(1)
    {
        scanf("%d%d%d",&z,&x,&y);
        if(x==0&&y==0&&z==0)
            break;
        l=0;
        r=0;
        memset(j,0,sizeof(int)*31*31*31);
        for(c=0;c<z;c++)
        {
            for(a=0;a<x;a++)
            {
                scanf("%s",g[c][a]);
            }
        }
        for(c=0;c<z;c++)
        {
            for(a=0;a<x;a++)
            {
                for(b=0;b<y;b++)
                {
                    if(g[c][a][b]=='S')
                    {
                        j[c][a][b]=1;
                        d[r].z=c;
                        d[r].x=a;
                        d[r++].y=b;
                        int k=bfs();
                        if(k!=0)
                        {
                            printf("Escaped in %d minute(s).\n",k-1);
                        }
                        else
                        {
                            printf("Trapped!\n");
                        }
                    }
                }
            }
        }
    }
    return 0;
}

 

解题思路

这道题遍历即可解决,但如果使用纯暴力会超时计算量太大,所以要用二进制遍历.

因为每翻一次周围的也会跟着翻一次,而且如果某一个瓷砖翻两次就相当于没有进行翻动,所以我们可以对第一行进行一个假设.假设第一行每个瓷砖的翻面次数,对第一行进行翻面后如果第一行还有黑色存在那必然是这个瓷砖下面的瓷砖进行了翻面.如果到最后一行进行翻面后还有黑色瓷砖则代表第一行翻面次数不对.

PS:这道题目因为可能有多个答案所以还要考虑比较翻面次数,只取翻面次数最小的.

代码

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
using namespace std;
int g[20][20];
int j[20][20];
int gg[20][20];
int jj[20][20];
int ne[6][2]={{1,0},{-1,0},{0,1},{0,-1},{0,0}};
int h[20];
int n,m;
int k;
int dfs(int i)
{
    for(int y=0;y<n;y++)
    {
        if(j[i][y]==1)
        {
            for(int x=0;x<5;x++)
            {
                int tx=i+ne[x][0];
                int ty=y+ne[x][1];
                if(tx<0||tx>=m||ty<0||ty>=n)
                    continue;
                if(gg[tx][ty]==0)
                {
                    gg[tx][ty]=1;
                }
                else
                {
                    gg[tx][ty]=0;
                }
            }
        }
    }
    if(i+1==m)
    {
        for(int y=0;y<n;y++)
        {
            if(gg[i][y]==1)
                return 0;
        }
        return 1;
    }
    for(int y=0;y<n;y++)
    {
        if(gg[i][y]==1)
        {
            j[i+1][y]=1;
        }
    }
    return dfs(i+1);
}
void cls()
{
    for(int x=0;x<m;x++)
    {
        for(int y=0;y<n;y++)
        {
            gg[x][y]=g[x][y];
        }
    }
    memset(j,0,sizeof(int )*20*20);
}
int main()
{
    int x,y,mi=999999;
    scanf("%d%d",&m,&n);
    for(x=0;x<m;x++)
    {
        for(y=0;y<n;y++)
        {
            scanf("%d",&g[x][y]);
        }
    }

    for(x=0;x<1<<n;x++)
    {
        k=0;
        cls();
        for(y=0;y<n;y++)
        {
            j[0][y]=h[y];
        }
        k=dfs(0);
        if(k!=0)
        {
            k=0;
            for(int l=0;l<m;l++)
            {
                for(int r=0;r<n;r++)
                {
                    if(j[l][r]==1)
                        k++;
                }
            }
            if(k<mi)
            {
                mi=k;
                for(int l=0;l<m;l++)
                {
                    for(int r=0;r<n;r++)
                    {
                        jj[l][r]=j[l][r];
                    }
                }
            }
        }
        int d=n-1;
        h[d]+=1;
        while(h[d]==2)
        {
            h[d]=0;
            d--;
            h[d]++;
        }
    }
    if(mi==999999)
    {
        printf("IMPOSSIBLE");
    }
    else
    {
        for(x=0;x<m;x++)
        {
            for(y=0;y<n;y++)
            {
                printf("%d ",jj[x][y]);
            }
            printf("\n");
        }
    }
    return 0;
}

解题思路

简单的dfs就可以解决,我们只要每遇到石油就将与它相邻的石油打上标记就好.

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
using namespace std;
char g[110][110];
int ne[9][2]={{1,0},{-1,0},{0,1},{0,-1},{-1,-1},{1,-1},{-1,1},{1,1}};
int n,m;
int dfs(int x,int y)
{
    int tx,ty,z;
    for(z=0;z<8;z++)
    {
        tx=ne[z][0]+x;
        ty=ne[z][1]+y;
        if(tx<0||tx>m||ty<0||ty>n)
            continue;
        if(g[tx][ty]=='@')
        {
            g[tx][ty]='*';
            dfs(tx,ty);
        }
    }
    return 0;
}
int main()
{
    int sum=0;
    while(1)
    {
        sum=0;
        scanf("%d%d",&m,&n);
        //getchar();
        if(n==0&&m==0)
            break;
        for(int x=0;x<m;x++)
        {
            scanf("%s",g[x]);
            //getchar();
        }
        for(int x=0;x<m;x++)
        {
            for(int y=0;y<n;y++)
            {
                if(g[x][y]=='@')
                {
                    g[x][y]='*';
                    dfs(x,y);
                    sum++;
                }
            }
        }
        printf("%d\n",sum);
    }
    return 0;
}

java

我初步了解了java的基本语法,基本的数据类型和数组的定义与运用.


http://www.kler.cn/a/274570.html

相关文章:

  • Vue3之状态管理Vuex
  • STM32, GD32 cubemx CAN 低速率125kbps 报文丢失,解决了
  • 数据结构大作业——家谱管理系统(超详细!完整代码!)
  • javaFX.(蜜雪冰城点餐小程序)MySQL数据库
  • 厦门凯酷全科技有限公司短视频带货可靠吗?
  • 迈向未来:.NET技术的持续创新与发展前景
  • React状态管理库快速上手-Redux(一)
  • 2024.3.19
  • WebSocket 和SSE的区别以及优缺点
  • publicPath 和 __webpack_public_path__ 和 process.env.BASE_URL的区别和使用方法
  • 使用Vscode连接云进行前端开发
  • Java使用itextpdf往pdf中插入图片
  • nodejs 使用express插件multer文件上传,接收不到文件的bug
  • 未来汽车EE架构趋势
  • 数库据设计最佳实践
  • React——关于表单元素
  • C#,图论与图算法,计算无向连通图中长度为n环的算法与源代码
  • 湖北省地质灾害分布数据 崩塌滑坡泥石流空间分布地质灾害详查等数据集
  • Spark-Scala语言实战(3)
  • Linux:Gitlab:16.9.2 创建用户及项目仓库基础操作(2)
  • xAI开发的一款巨大型语言模型(HLM)--Grok 1
  • Hive 使用 LIMIT 指定偏移量返回数据
  • 力扣--回溯算法51.N皇后
  • Stable Diffusion WebUI 生成参数:高清修复/高分辨率修复(Hires.fix)
  • web前端之不一样的下拉菜单、不选中第一个元素的样式效果、伪类排除第一个元素、符号选择器、hover、not、first、child
  • 【AIGC调研系列】MetaGpt与AutoGpt相比有哪些优势和劣势