-
2012-10-31 13:24:58
按照九宫格的方式画九个点,每个点与上下左右相邻的点的距离相等。
如下:
● ● ●
● ● ●
● ● ●问用一笔画四条直线将所有的点连接起来。(也就是除了第一条直线起始和最后一条直线结束外,每条直线必须首尾相连。)
更多相关内容 -
贴吧趣味问题——一线连24点【编程穷举证明无解】
2020-03-23 15:23:14逛贴吧的时候遇到了一个趣味问题 这里我再重复一遍问题 如下图所示,不过黑点,把所有白色圆圈用一条线连起来,不能重复,不能斜着连(更不能像上图那样穿墙传送) 把上图用矩阵文本表示出来如下(0代表黑点,即不...逛贴吧的时候遇到了一个趣味问题
这里我再重复一遍问题
如下图所示,不过黑点,把所有白色圆圈用一条线连起来,不能重复,不能斜着连(更不能像上图那样穿墙传送)
把上图用矩阵文本表示出来如下(0代表黑点,即不能连的点):1, 0, 1, 1, 1 1, 1, 1, 1, 1 1, 1, 1, 1, 1 1, 1, 1, 1, 1 1, 1, 1, 1, 1
1-思路分析
倘若问题有解,即能够一条线连接所有点
那一条线必然有两个端点,由于左上角的1只有一个相邻点可以连接,必然为一个端点(非端点必须是起码有两个可以连接的相邻点的)
不妨以左上角的1为起点去探索,如果递归尝试所有方向后均不能一条线连接所有点,则说明该问题无解2-递归实现代码(回溯法)
这里的代码思路和我之前的博客:【教程】python递归三部曲(基于turtle实现可视化)-三、迷宫探索基本是一样的
感兴趣的话,也可以对比着看看
一条线连的探索过程为:
从起点(左上角的1)出发,分别按顺序往上下左右四个方向去探索(即连接上下左右的可以连接的相邻点),
在这一过程中递归地对连接后的相邻点进行进一步四周的探索(即将该相邻点当做新的起点去执行上一步骤,直至探索完成或失败,才开始下一个方向的探索)
探索的具体过程可以分下面几种情况:- 该点不可连接(黑点或已经连接过的点)或超出边界,告诉上一步这一步探索失败
- 没有可以连接的点了,但a) 连完了所有点,探索完成,告诉上一步这一步探索成功 ,b)没连完所有点,探索失败,然后告诉上一步这一步探索是失败的
- 向某个方向的探索得出的结论是成功的,那么探索完成,不在探索,并且告诉上一步探索这一方向是能够探索成功的
- 向某个方向的探索得出的结论是失败的,那么换一个方向进行探索
结合以上分析,可以写出探索的递归方法
searchNext
,全部代码如下problem_board = [ [1, 0, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1] ] def check_all_linked(board): for row in board: for v in row: if v == 1: return False return True def search_next(board, ci, ri, v): # 1. 该点不可连接(黑点或已经连接过的点)或超出边界,告诉上一步这一步探索失败 if not (0 <= ci < len(board[0]) and 0 <= ri < len(board)): # 超出边界 return False if board[ri][ci] != 1: # 黑点或已经连接过的点 return False board[ri][ci] = v + 1 direction = [ (1, 0), (0, -1), (-1, 0), (0, 1), ] for d in direction: dc, dr = d found = search_next(board, ci + dc, ri + dr, v+1) if found: # 3. 向某个方向的探索得出的结论是成功的,那么探索完成,不在探索,并且告诉上一步探索这一方向是能够探索成功的 return True else: # 4. 向某个方向的探索得出的结论是失败的,那么换一个方向进行探索 pass # 2. 没有可以连接的点了 # a) 连完了所有点, 探索完成,告诉上一步这一步探索成功 if check_all_linked(board): return True # b)没连完所有点**,探索失败,然后告诉上一步这一步探索是失败的 board[ri][ci] = 1 return False r = search_next(problem_board, 0, 0, 1) print(r)
输出为
False
3-turtle实现可视化
import turtle # 建立窗体 SCR = turtle.Screen() SCR.setup(800, 800) # 设置窗体大小 radius = 40 distance = 120 problem_board = [ [1, 0, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1] ] simple_problem_board_0 = [ [1, 0, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1], ] simple_problem_board_1 = [ [1, 0, 1], [1, 1, 1], [1, 1, 1] ] dot_t = turtle.Turtle() dot_t.hideturtle() dot_t.speed(0) dot_t.width(2) link_t = turtle.Turtle() link_t.hideturtle() link_t.pensize(5) link_t.penup() link_t.speed(0) link_t.color("blue") def draw_white_dot(x, y): dot_t.penup() dot_t.goto(x, y - radius) dot_t.setheading(0) dot_t.pendown() dot_t.circle(radius) def draw_black_dot(x, y): dot_t.penup() dot_t.goto(x, y - radius) dot_t.setheading(0) dot_t.pendown() dot_t.begin_fill() dot_t.circle(radius) dot_t.end_fill() def draw_board(board): r = len(board) c = len(board[0]) width = (r-1) * distance height = (c-1) * distance sx = - width // 2 sy = height // 2 link_t.goto(sx, sy) link_t.pendown() for ri in range(r): for ci in range(c): xi = sx + ci * distance yi = sy - ri * distance v = board[ri][ci] if v == 0: draw_black_dot(xi, yi) else: draw_white_dot(xi, yi) def check_all_linked(board): for row in board: for v in row: if v == 1: return False return True def search_next(board, ci, ri, v, di): # 1. 该点不可连接(黑点或已经连接过的点)或超出边界,告诉上一步这一步探索失败 if not (0 <= ci < len(board[0]) and 0 <= ri < len(board)): # 超出边界 return False if board[ri][ci] != 1: # 黑点或已经连接过的点 return False if v > 1: link_t.setheading(di * 90) link_t.forward(distance) board[ri][ci] = v + 1 # 必须按照右上左下的顺序,与画笔方向才能一致 direction = [ (1, 0), (0, -1), (-1, 0), (0, 1), ] for i, d in enumerate(direction): dc, dr = d found = search_next(board, ci + dc, ri + dr, v+1, i) if found: # 3. 向某个方向的探索得出的结论是成功的,那么探索完成,不在探索,并且告诉上一步探索这一方向是能够探索成功的 return True else: # 4. 向某个方向的探索得出的结论是失败的,那么换一个方向进行探索 pass # 2. 没有可以连接的点了 # a) 连完了所有点, 探索完成,告诉上一步这一步探索成功 if check_all_linked(board): return True # b)没连完所有点**,探索失败,然后告诉上一步这一步探索是失败的 board[ri][ci] = 1 for _ in range(2): link_t.undo() return False # draw_board(simple_problem_board_1) # search_next(simple_problem_board_1, 0, 0, 1, 0) # draw_board(simple_problem_board_0) # search_next(simple_problem_board_0, 0, 0, 1, 0) draw_board(problem_board) search_next(problem_board, 0, 0, 1, 0) turtle.done()
问题是回溯法的时间复杂度过高,所以导致这个绘制动画要耗时很久
这里在第四部做个优化4-可视化动画优化
在
search_next
方法中发现圆点已经被连线分成两个不相连的部分的时候,就已经可以说明当前的连线方式有问题,探索失败并通知上一步
故这里将第三部分的代码添加上advanced_search_next
方法,待添加的代码如下def check_board_separated(board): check_board = [row[:] for row in board] sr = -1 sc = -1 for ri in range(len(check_board)): for ci in range(len(check_board[0])): if check_board[ri][ci] == 1: sr = ri sc = ci break if sr >= 0: break if sr < 0: return False direction = [ (1, 0), (0, -1), (-1, 0), (0, 1), ] check_board[sr][sc] = 2 to_explore = [(sc, sr)] while len(to_explore) > 0: new_to_explore = [] for item in to_explore: ci, ri = item for i, d in enumerate(direction): dc, dr = d nc, nr = dc + ci, dr + ri if (0 <= nc < len(board[0]) and 0 <= nr < len(board)) and check_board[nr][nc] == 1: check_board[nr][nc] = 2 new_to_explore.append((nc, nr)) to_explore = new_to_explore for ri in range(len(check_board)): for ci in range(len(check_board[0])): if check_board[ri][ci] == 1: return True return False def advanced_search_next(board, ci, ri, v, di): # 1. 该点不可连接(黑点或已经连接过的点)或超出边界,告诉上一步这一步探索失败 if not (0 <= ci < len(board[0]) and 0 <= ri < len(board)): # 超出边界 return False if board[ri][ci] != 1: # 黑点或已经连接过的点 return False if v > 1: link_t.setheading(di * 90) link_t.forward(distance) board[ri][ci] = v + 1 if check_board_separated(board): board[ri][ci] = 1 if v > 1: link_t.undo() link_t.undo() return False # 必须按照右上左下的顺序,与画笔方向才能一致 direction = [ (1, 0), (0, -1), (-1, 0), (0, 1), ] for i, d in enumerate(direction): dc, dr = d found = advanced_search_next(board, ci + dc, ri + dr, v+1, i) if found: # 3. 向某个方向的探索得出的结论是成功的,那么探索完成,不在探索,并且告诉上一步探索这一方向是能够探索成功的 return True else: # 4. 向某个方向的探索得出的结论是失败的,那么换一个方向进行探索 pass # 2. 没有可以连接的点了 # a) 连完了所有点, 探索完成,告诉上一步这一步探索成功 if check_all_linked(board): return True # b)没连完所有点**,探索失败,然后告诉上一步这一步探索是失败的 board[ri][ci] = 1 for _ in range(2): link_t.undo() return False
最后调用时
把search_next
改为advanced_search_next
调用就好5 - 通过逻辑简单证明
实际上,有更简单的方法证明该问题是无解的
- 先把左上角的圆圈标为A
- A的上下左右相邻的可以连接的圆圈标为B
- B的上下左右相邻的可以连接的圆圈标为A
- 重复2、3步直至所有可以连接的圆圈都被标上A或B
如下图所示
图中有13个A,11个B
由于A只能连B,B只能连A,所以假设能一条线连接24个点的话(该线的一个端点必然为左上角的A点)
故该线段对应的必然是ABAB…这样AB交错的顺序,这种顺序,AB点的个数要么相等(如ABAB),要么A点比B点多1个点(如ABABA)
但是13个A点,11个B点,必然有起码一个A点是无法通过AB交错的方式连接起来,
即无法通过一条线来连接
-
下面有9个点的图片。你能一笔画出4条直线连接着9个点,并且不重复任何一条线吗?
2012-02-02 00:16:53 -
不过黑点,把所有圆圈连起来
2020-12-24 16:21:10公告: 为响应国家净网行动,部分内容已经删除,感谢读者理解。话题:不过黑点,把所有圆圈连起来。...我个人认为这道题的难点不是图片而是字,要不然 看谁聪明 那几个大字下面就一空白行做何用呢这么多大神都...公告: 为响应国家净网行动,部分内容已经删除,感谢读者理解。
话题:不过黑点,把所有圆圈连起来。不能斜着连!求解~
问题详情:说不能连黑点,没说不能绕开黑 |回答说简单,还没给出怎么走的回答:说不能连黑点,没说不能绕开黑点,看来确实很无解?只要从下面开始横着连,到上面遇到黑点的时候从上面空白处绕开即可!我个人认为这道题的难点不是图片而是字,要不然 看谁聪明 那几个大字下面就一空白行做何用呢这么多大神都说无解
参考回答:/zhidao/wh%3D600%2C00/sign=e16dca43ba315c6043c063ebd1e2b/cea15ce36d3d53b3653ce50352ab03d./zhidao/pic/item/cea15ce36d3d53b3653ce50352ab03d: b.hiphotos./zhidao/wh%3D450%2C600/sign=5f4cdedcd54e4be06063ebe6e/cea15ce36d3d53b3653ce50352ab03d.jpg" esrc=".话题:一笔能连成吗?不能重连,不能斜连,黑点不能连。回答:可以的,弯曲着连,可以一笔把所有圆圈都连起来
参考回答:不能,根本不能。话题:不过黑点,把所有的圆圈连接起来,不能重复,不能斜着连
问题详情:baidu.jpg" target="_blank" class="回答:第三行画竖线连接五空圆圈由左边起画竖线连接第五个空圆圈,第二行画竖线连接四空圆圈,不经黑点
参考回答:左上角起,上行、高过黑点右行、跨过黑点下行;右行至右上角;下行至右下角;左移一列、上行;左移一列、下行;左移一列、上行话题:图中黑点不能连,不能重复,不能用斜线,请问怎么将它们回答:不可能。用染色法可以证明。白色比黑色多了两块把左上角标为白色,然后相邻的为相反的颜色。白无白黑白黑白黑白黑白黑白黑白黑白黑白黑白黑白黑白除去不能走的那个点,一共有13个白块,11个黑块。假如存在一条连续的线,它是按一白一黑走的(因为不能斜着走),所以不可能一种颜色比另一种多两块。求采纳
参考回答:还可以更难点吗 比较简单的这个 一笔画下去就可以了啊无法上图 但这也太简单了 我直接告诉你怎么画 按围棋的格数 11 12 13 14话题:不能重复!一笔连下来!不能过黑点!不能斜着连。回答:这有什么难的,从左边的上边开始到右边转圈连就可以啦!
参考回答:从黑点向左向斜向左一直这样连,很简单的话题:不过黑点,把所有圈圈连接,不能重复,不能斜着连
问题详情:/zhidao/wh%3D450%2C600/sign=bea2e6b224f4a5ccb回答:.hiphotos.jpg" /这样可以不 不能重复是指线不能重复呢还是圆圈不能重复.jpg" esrc=": a? |
参考回答:你说不能斜着连不能重复连没说连线不能跑出外面啊话题:如何做到不碰到黑点一笔不斜不重复的把其他全连在一起
问题详情:求 知道的大神告诉下 如何做到不碰到黑点一笔不斜不重复的把其回答:我也解了两天了,妹的,根本无解!话题:不过黑点,不能斜着怎么把圆圈都连上回答:不过黑点,不能斜着怎么把圆圈都连上话题:不过黑点,把所有圆圈连起来,不能重复,不能斜
问题详情:baidu.baidu.hiphotos./zhidao/wh%3D600%2C00/sign=1b4a回答:太简单了……话题:不过黑点,一条线把剩下所有的圆圈连起来,不可重复,不可
问题详情:不能交叉不能越界不能碰到黑点 |总会多个白点,求答 |简回答:并只在白点上转移,并只限纵横方向连接,并已转移过得白点不能再次经过,这个不可能达到所有线都有白线经过说明白一些,假如是说“线从任意白点开始,从而达到所有白点都有线经过”的话
参考回答:无论怎么样连 根据你的则都不能成立 这题本身就是错的连不上 无法成立
-
如何用四条直线把这9个点连起来,要求这四条直线是连续的
2017-11-09 11:58:00如何用四条直线把这9个点连起来,(要求这四条直线是连续的)。 说明:这个题目容易让人误解,理解可能有偏差,这里再解释一下,就是有上面9个点的布局,怎么用4条直线链接,除起点和终点外,保证一条直线尾都另一条... -
visio技巧(曲线、连接点、自制模具)
2021-05-25 16:02:12这里写自定义目录标题欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、... -
百度AI人脸识别(面部器官分组及关键点连接)
2020-06-06 15:52:30//重置连接点到当前连接点 x_1 = (int) nowFaceLocation.getX(); y_1 = (int) nowFaceLocation.getY(); } } } } //生效 mark_rag.dispose(); //生效 joint_rag.dispose(); //创建图片 String locaPath = request.... -
【计算机图形学】一笔绘制金刚石图案
2020-03-04 02:00:04第一篇自己的CSDN博客!!! 在CSDN上抄了一年多作业, 终于要自己发博客啦233333,但是并没有什么含金量的其实嘤嘤嘤QAQ 想码一些作业当时做完有点成就感的作业吧,毕竟以我个人的水平和热爱学习的程度可能上学期间... -
笔记本连接不上外接显示器_如何将多个外接显示器连接到笔记本电脑
2020-09-07 11:41:30笔记本连接不上外接显示器Multiple monitors are awesome. They really are—ask anyone who’s used a two- or three-screen setup for their desktop, and they’ll tell you that they have a hard time going ... -
用python写一个脚本,自动连wifi,自动登录校园网
2022-06-02 19:35:01自动连接wifi,自动登录校园网,打包exe文件。 -
可以嵌入ppt的课堂点名器_让你相见恨晚的30个PPT技巧
2020-12-03 17:26:3701 一键替换全部A字体为B字体 当我们做好了一个PPT,却突然发现里面的字体用的不够好的时候,【替换字体】功能可以帮我们省去一页一页、甚至一个文本框一个文本框去修改字体的痛苦。替换字体功能点击【开始】选项..... -
Qt快速绘制像素点的处理方法
2018-12-13 16:12:09比如我之前模拟写的一个渲染管线开源练习,涉及到了大量的像素点操作。而Qt本身的QPen和QPainter::drawPoint的API如果操作大量的像素点,会非常耗时,因此我Google了这个方式: 原文链接:... -
三星p600平板电脑无法连接无线网络该怎么办?
2021-08-04 02:51:16一说三星平板,小编第一时间就想到自己的第一款三星p600平板,P600是10.1寸的平板,当时这款平板还是很不错的,可以拿来看看书、看看视频、浏览浏览网页什么的,但是随着时间的增长,平板的电池越来月不行了,已经将... -
【和冠 Bamboo CTL-672/K2-F 数位板使用总结】连接|便携|绘画_摘要频道_什么值得买
2021-01-12 17:51:32和冠 Bamboo CTL-672/K2-F 数位板使用总结(连接|便携|绘画)连接电脑,首先登录wacom官网下载驱动程序并安装。软件安好后可以根据自己的习惯来设置数位笔的快捷键,我分享下我的设置。下键是双击,上键是右键单击,... -
基于大模型,开发一款AI图片生成器丨“悟道之巅”公开课干实录(5)
2021-12-03 17:21:34如果你错过了上一波深度学习引发的NLP范式转换,不要再错过这一波超大预训练模型的崛起。 近日,“悟道”核心团队推出首档公开课,公开课已全部...第二讲视频点此观看 第三讲视频点此观看 第四讲视频点此观看 第五讲视 -
触控笔的这些技巧,你都get到了吗?
2020-12-18 19:20:45但是大家也别忽略了联想送出的配套产品——触控笔!它身上的亮点也不少,而且它和电子墨水屏的联动功能,堪称天作之合呀!1.png46378702019-6-3 00:03 上传购入联想YOGA Book 2后,你会发现配套送出的手写笔在使用... -
负载均衡的会话保持和长短连接简介
2019-04-16 17:05:44图片来源:王朝阳 简单来说 会话保持是指连接断开,在规定时间内再次连接的时候,保证路由到同一服务器。而长连接在keep-alive状态下,也是会路由到同一服务的。会话不保持的话,连接断开,再次连接的时候,会重新... -
计算图片的相似度(深度学习)
2018-11-17 15:08:23一、相关理论 ...本篇博文主要讲解2015年CVPR的一篇关于图像相似度计算的文章:《Learning to Compare Image Patches via Convolutional Neural Networks》,本篇文章对经典的算法SiameseNetworks... -
【历史上的今天】10 月 15 日:FORTRAN 语言正式问世;支付宝诞生第一笔交易;Tcl 语言发明者出生
2021-10-14 09:47:3810 月 15 日,历史上的今天,互联网标准的奠基人 Steve Crocker 出生;脚本语言 Tcl 的发明者 John Ousterhout 出生;...支付宝诞生第一笔交易;Adobe Photoshop CS4 发布;谷歌发布智能手机 Pixel 5 。 -
一个合格的初级前端工程师需要掌握的模块笔记
2021-02-04 09:43:23一个合格的初级前端工程师需要掌握的模块笔记 文章目录一个合格的初级前端工程师需要掌握的模块笔记前言Web模块html基本结构标签属性事件属性文本标签多媒体标签列表表格表单标签其他语义化标签网页结构模块划分CSS... -
SoC FPGA全连接神经网络实现数字手写体识别
2021-12-16 14:21:35SoC FPGA全连接神经网络实现数字手写体识别 一、全连接神经网络-DNN 1、网络结构 2、神经网络的训练 3、反向传播算法BP ...DNN的结构不固定,一般神经网络包括输入层、隐藏层和输出层,一个DNN结构只有一个输入层 -
java 创建新的图片,底色自己设定
2019-04-01 16:35:24我的需求是:在照片下方加上照片描述. 思路: 1,先创建与照片宽度一样的白底图片...一:创建图片 package tuPian; import java.awt.Color; import java.awt.Graphics; import java.awt.image.BufferedImage; impor... -
java 把头像图片剪切成圆图 并在头像后面加一个白圆圈
2018-07-10 14:44:55public static void main(String[] args) throws ... //从链接中获取图片,如OSS,服务器等。 // String url = "https://mjmall.oss-cn-shanghai.aliyuncs.com/18/1/merchantIcon.png"; // BufferedIm... -
java连接打印机
2019-07-11 20:26:33使用连接线选择usb端口,完成后可以打印空白页进行测试。刚开始的时候因为找不到连接线,我使用笔记本蓝牙进行连接,选用串口com4连接,也可以进行打印。 得力打印机 下载驱动,配置端口,安装驱动。 后台 pom.... -
电容的电路符号及图片识别
2021-01-17 11:23:303.耦合:作为两个电路之间的连接,允许交流信号通过并传输到下一级电路4.滤波:这个对DIY而言很重要,显卡上的电容基本都是这个作用。5.温度补偿:针对其它组件对温度的适应性不够带来的影响,而进行补偿,改善... -
java图片上传同时后台直接给MultipartFile对象添加图片水印或者文字水印,然后直接上传带水印的图片
2018-11-30 11:51:59本文只介绍给文件上传对象...1.图片水印 1.先上工画图片水印的方法 /** * 加图片水印 * * @param bufImg --BufferedImage 用来画图的宽高跟需要加水印的图片一样的空白图 * @param img --... -
PyQt5 绘制画 线(鼠标笔)
2020-12-29 15:39:24文章目录1、简介2、功能实现1、简介通过多鼠标事件的监听、绘制事件的监听,实现一个鼠标笔 2、功能实现# -*- coding: utf-8 -*-"""【简介】使用paintEvent在窗口实现划线例子"""import sysfrom PyQt5.QtWidgets ... -
ESP8266+STM32F407+OV7670实现图片传输
2020-04-29 10:10:14声明:由于ESP8266与STM32之间采用串口进行通讯,导致传输速率较低,一到两秒才可以传输一帧图片,因此无法实现实时的图像显示。 本文虽然以串口通讯的方式进行数据传输,但是建议想要实现实时视频显示的... -
intellij idea写Springboot生成图片验证码两种实现方式(全码)
2019-02-12 09:54:45最近工作中,需求让新加一个图片验证码功能,其实这个功能之前自己写过,想必跟大家现在心里想到的实现方式一样,要么是通过servlet实现请求操作,要么是通过get请求实现操作。然后在后台通过session存储图片上的... -
Android 实现系统打印机打印图片,文本,以及二维码生成与解析
2020-06-19 16:44:551、使用系统打印机打印图片: /**系统打印机--打印图片*/ private void doPrintPictures(Bitmap bitmap) { PrintHelper photoPrinter = new PrintHelper(this); photoPrinter.setScaleMode(PrintHelper.SCALE_...