每日总结(2022/1/12)_坐也思钧的博客-程序员宅基地

技术标签: 算法  深度优先  笔记  蓝桥杯  

1.上午(2h)

将bfs看了很多遍,把涂色题码了一大半,但是还是差一点过

题目描述

由数字00组成的方阵中,有一任意形状闭合圈,闭合圈由数字11构成,围圈时只走上下左右44个方向。现要求把闭合圈内的所有空间都填写成22.例如:6 \times 66×6的方阵(n=6n=6),涂色前和涂色后的方阵如下:

0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1

输入格式

每组测试数据第一行一个整数n(1 \le n \le 30)n(1≤n≤30)

接下来nn行,由00和11组成的n \times nn×n的方阵。

方阵内只有一个闭合圈,圈内至少有一个00。

//感谢黄小U饮品指出本题数据和数据格式不一样. 已修改(输入格式)

输出格式

已经填好数字22的完整方阵。

输入输出样例

输入 #1复制

6
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1

输出 #1复制

0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1

说明/提示

1 \le n \le 301≤n≤30

这道题和其他涂色题相比是有可以投机取巧的地方的

可以先把最外层加一圈0,然后将0分成两种,一种是在1圈外面的,另一种就是在1圈里面的,由于题目的表述限制,是可以过的

#include<stdio.h>
int n;
int map[35][35];//地图
int vis[35][35];//标记
int fx[4]={0,0,-1,1};//移动
int fy[4]={1,-1,0,0}; 
void dfs(int x, int y)
{
	if(x<0||y<0||x>n+1||y>n+1||vis[x][y]!=0)//判断是否越界或者为墙
	return ;
	vis[x][y]=1;//标记
	for(int i=0;i<=3;i++)
	dfs(x+fx[i],y+fy[i]);//进一步搜
}
int main()
{
	scanf("%d",&n);//输入
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	{
		scanf("%d",&map[i][j]);//输入地图
		if(map[i][j]==0)
		vis[i][j]=0;
		else
		vis[i][j]=2;//方便打印
	}
	dfs(0,0);
	for(int i=1;i<=n;i++)//打印格式
	{
		for(int j=1;j<=n;j++)
		{
			if(vis[i][j]==0)//已经搜到了
			printf("2 ");
			else
			printf("%d ",map[i][j]);
		}
		printf("\n");
	}
}

2.下午一直到傍晚(7h)

解决了马的遍历

题目描述

有一个 n \times mn×m 的棋盘,在某个点 (x, y)(x,y) 上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步。

输入格式

输入只有一行四个整数,分别为 n, m, x, yn,m,x,y。

输出格式

一个 n \times mn×m 的矩阵,代表马到达某个点最少要走几步(左对齐,宽 55 格,不能到达则输出 -1−1)。

输入输出样例

输入 #1复制

3 3 1 1

输出 #1复制

0    3    2    
3    -1   1    
2    1    4    

说明/提示

数据规模与约定

对于全部的测试点,保证 1 \leq x \leq n \leq 4001≤x≤n≤400,1 \leq y \leq m \leq 4001≤y≤m≤400。

这道题我看了很久的题解才敲出去。。。

#include<cstdio>
#include<cstring>
#include<queue>
#include<iomanip>
using namespace std;
const int N=501;

int a[N][N];//定义501*501的储存答案的数组

struct point{
	int x;
	int y;
	int t;
};//广搜结构体,对于每一个点,要储存它的横坐标(x坐标),纵坐标(y坐标),当前所走的步数

queue<point> que;//广搜必备队列,C++STL万岁O(∩_∩)O~~
int n,m,sx,sy;//棋盘边界、出发点坐标。

int dx[8]={-2,-2,-1,-1,2,2,1,1};
int dy[8]={1,-1,2,-2,1,-1,2,-2};//坐标偏移量

int main()
{
	memset(a,-1,sizeof(a));//答案数组全部赋值-1,能达到就改为当前步数,不能改就直接输出。
	scanf("%d%d%d%d",&n,&m,&sx,&sy);
	a[sx][sy]=0;//切记,一定要把起点赋值为0,否则全WA
    
    //广搜
	que.push((point){sx,sy,0});//将起点放入队列
	while(!que.empty())//只要还有可以走的点,就继续执行
	{
		point f=que.front();//将当前点拿出来
		que.pop();//扔掉当前点
        
		for(int i=0;i<=7;i++)//遍历当前点所能走到的其它点
		{
			int nx=f.x+dx[i];
			int ny=f.y+dy[i];//通过坐标偏移量得到可以走的点的坐标
			if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[nx][ny]==-1)//当前点既没超出棋盘范围又还没有走过
			{
				a[nx][ny]=f.t+1;//这个点的答案就是上一个点的答案+1辣
				que.push((point){nx,ny,f.t+1});//当前点可行,我们将其放入队列
			}
		}
	}
    //滑稽的输出
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			printf("%-5d",a[i][j]);
		}
		printf("\n");
	}
	return 0;//完美~^_^
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_62494553/article/details/122461368

智能推荐

AppBarLayout中android:fitsSystemWindows="true"无效的解决办法_FzQqq.的博客-程序员宅基地

因为在AppBarLayout中对android:fitsSystemWindows进行了修改,故不能正常实现android:fitsSystemWindows="true"的效果。为了实现沉浸式的一种效果,我在ToolBar里设置了android:paddingTop属性,来抵消掉系统自带状态栏的空间,使ToolBar中内容得以不向上陷入系统状态栏。 &lt;android.support...

ios检测摄像头、指南针、陀螺仪的状态的代码_渡壑的博客-程序员宅基地

//检查前后摄像头- (void)cameraBtnAction:(id)sender{ BOOL cameraAvailable = [UIImagePickerController isCameraDeviceAvailable: UIImagePickerControllerCameraDevi

Glide 4.6.x以上 回调设置Bitmap对象_jia635的博客-程序员宅基地

Glide 3.x版本的时候还有load(url).asBitmap 方法,到4.x的时候这个方法就不存在了,如果通过Glide获取Bitmap,这可以通过SimpleTarget 是去实现。// 设置背景public static void loadImageInbackGround(Context context, String url, View view, int defResId) {...

(C语言版)链表(一)——实现单向链表创建、插入、删除等简单操作(包含个人理解说明及注释,新手跟着写代码)_sinat_35297665的博客-程序员宅基地

http://blog.csdn.net/fisherwan/article/details/19701027我学习了几天数据结构,今天下午自己写了一个单向链表的程序。我也是新手,所以刚开始学习数据结构的菜鸟们(有大牛们能屈尊看一看,也是我的荣幸)可以和我一起共同学习、讨论,当然也很高兴能指出我的错误,因为这是我们一起成长的过程。本代码包含我在写程序时的一些个人理解的说明和一些注释(如

对sklearn文件pyd文件进行修改的方法_rnf的博客-程序员宅基地_如何修改sklearn源代码

首先声明这篇文章没有原理解释,只有遇到的各种问题和个人解决方案。为什么要修改pyd文件,因为我想要修改sklearn里随机森林的决策树构建算法,这部分的关键代码为了提高运行效率被放到了pyd文件中。pyd文件本质是一种python的dll文件,所以无法直接编写。解决方案就是通过setuptools从.pyx文件中生成pyd。平台:windows10python版本:python3.7以下是打包用到的setup.py文件from setuptools import setupf...

Python的__iter__和__getitem___weixin_44865913的博客-程序员宅基地

Python的__iter__和__getitem__iter( ) 与 __ iter__ 用于产生 iterator(迭代器)__ iter__ 迭代器协议凡是实现__iter__协议的对象,皆是迭代器对象。(next()也得实现,不然没法产生数据)Iter()迭代器工厂函数凡是有定义有__iter__()函数,或者支持序列访问协议,也就是定义有__getitem__()函数的对象 ...

随便推点

Linux下Apache正常配置下仍然503的解决办法_墨气的博客-程序员宅基地

工作中用到了Apache做反向代理,配置好后遇到了503的问题,再次作为记录,我采用的是方法一并验证可行。Linux 环境下,Apache 正常安装,httpd.conf也已正常配置,经测试80端口也已开通,但在外网测试时仍然是提示503错误。经过查资料和分析怀疑是SELinux的原因,于是查看果然是: 原因:Liunx命令代码  [[email protected] logs]# /usr/sbin

oracle clob与nclob的互相转换_weixin_34174105的博客-程序员宅基地

drop table clobTets create table clobTets( col1 nclob ) select * from clobTets insert into clobTets values('11111') alter table clobTets add (col2 varchar2(4000)) update clobTets set ...

Jenkins构建Job,通过Extended E-mail Notification发送邮件时遇到的问题_Jorah_Bronn的博客-程序员宅基地

**最近在测试服务器上搭建了Jenkins,实现了Jenkins+Git+Robotframework自动化脚本的持续集成,然后在jenkins创建slave agent在本地的机器跑脚本,遇到了问题总结一下。**问题一: 邮件结果展示不出来 因为有同事离职后,脚本跑不起来了,尤其是邮件结果展示不出来: 刚开始以为是邮件的H5代码出现了问题,检查之后发现别的机器也能跑,而后又检...

@service注解_周达的博客-程序员宅基地_service注解参数

@Service注解的使用首先,在applicationContext.xml文件中加一行:&lt;context:component-scan base-package="com.hzhi.clas"/&gt; 加上这一行以后,将自动扫描路径下面的包,如果一个类带了@Service注解,将自动注册到Spring容器,不需要再在applicationContext.xml文件定义be...

总结一下Meta的用法及robot.txt的讲解【转载】_Ancky的博客-程序员宅基地

总结一下Meta的用法及robot.txt的讲解Tue, 2006-05-23 02:44 — EvanceCopyrightauthorization: 原创做网页做久了一些不受注意的东西的也不得不去了解一下了..上网查找了一下robots.txt的用法,却一个不留神查到了关于meta的一些用法,觉得挺有用的,把详细的用法写出来了关于Meta的

1057. 数零壹(20)_-初心不负-的博客-程序员宅基地

给定一串长度不超过105的字符串,本题要求你将其中所有英文字母的序号(字母a-z对应序号1-26,不分大小写)相加,得到整数N,然后再分析一下N的二进制表示中有多少0、多少1。例如给定字符串“PAT (Basic)”,其字母序号之和为:16+1+20+2+1+19+9+3=71,而71的二进制是1000111,即有3个0、4个1。输入格式:输入在一行中给出长度不超过105、以回车结束的字符串。输出格