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

算法练习-搜索 相关

文章目录

  • 迷宫问题

迷宫问题

定义一个二维数组 m行 * n列 ,如 4 × 5 数组下所示:

int arr[5][5] = {
0, 1, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
};

它表示一个迷宫,1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,找出从左上角到右下角的路线。入口点为[0,0],既该点是可以走的路。

输入描述:
输入两个整数,分别表示二维数组的行数,列数。再输入相应的数组,其中的1表示墙壁,0表示可以走的路。数据保证有唯一解,不考虑有多解的情况,即迷宫只有一条通道。

输出描述:
左上角到右下角的最短路径,格式如样例所示。

示例1
输入:
5 5
0 1 0 0 0
0 1 1 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
输出:
(0,0)
(1,0)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(3,4)
(4,4)
 
示例2
输入:
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 1
0 1 1 1 0
0 0 0 0 0
输出:
(0,0)
(1,0)
(2,0)
(3,0)
(4,0)
(4,1)
(4,2)
(4,3)
(4,4)

python,广度优先

  • 每个点在条件允许的情况下搜索左右上下四个方向;
  • 走到一个点后,递归搜索剩下的路;
  • 最后输出字符串;
def start_to_walk(i, j, pos=[(0,0)]):if j + 1 < n and arr[i][j+1] == 0:# 可以向右if (i, j+1) not in pos:start_to_walk(i, j+1, pos+[(i,j+1)])if j >= 1 and arr[i][j-1] == 0:if (i, j-1) not in pos:start_to_walk(i, j-1, pos+[(i, j-1)])if i + 1 < m and arr[i+1][j] == 0:if (i+1, j) not in pos:start_to_walk(i+1, j, pos+[(i+1, j)])if i >= 1 and arr[i-1][j] == 0:if (i-1, j) not in pos:start_to_walk(i-1, j, pos+[(i-1, j)])if (i,j) == (m-1, n-1):for p in pos:print("("+str(p[0])+","+str(p[1])+")")while True:try:m, n = input().strip().split()m = int(m)n = int(n)arr = []for m_ in range(m):temp = input().strip().split()temp = list(map(int, temp))arr.append(temp)start_to_walk(0,0)except:break

相关文章:

算法练习-搜索 相关

文章目录 迷宫问题 迷宫问题 定义一个二维数组 m行 * n列 &#xff0c;如 4 5 数组下所示&#xff1a; int arr[5][5] { 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, }; 它表示一个迷宫&#xff0c;1表示墙壁&#xff0c;0表示可以走的路&#xff0c;只…...

PyQt5控件布局管理

Qt Designer提供了四种窗口布局&#xff1a;Vertical Layout(垂直布局) &#xff0c;Horizontal Layout(水平布局)&#xff0c;Grid Layout(栅格布局)&#xff0c;Form Layout(表单布局)&#xff0c;以及一种隐藏的布局—绝对布局 一般进行布局有两种方式&#xff1a; 一是通…...

TypeScript 一分钟让你理解泛型是什么

TypeScript 一分钟让你理解 泛型是什么 TS的泛型是指在定义函数、接口或类型时&#xff0c;不预先指定具体的类型&#xff0c;而是在使用时指定类型限制的一种特性。 泛型和函数中的参数比较类似&#xff0c;我们定义一个函数的时候有时会给它留一个参数名&#xff0c;在使用这…...

PatchMatchNet 训练dtu数据集、训练曲线查看、实操教程图图文详解、

文章目录 1 查看要求 下载数据集2 训练2.1 路径配置2.2 训练2.3 模型输出 与 训练曲线查看2.4 输出训练 log文件1 查看要求 下载数据集 在代码文件加下打开 README.md文件找到训练说明,查看那要求、下载训练集、训练方法 ## Training Download pre-processed [DTUs trainin…...

怎样制定测试计划和设计测试用例?

测试工作贯穿于整个软件开发生命周期&#xff0c;是一项庞大而复杂的工作&#xff0c;需要制订一个完整且详细的测试计划作为指导。测试计划是整个测试工作的导航图&#xff0c;但它并不是一成不变的&#xff0c;随着项目推进或需求变更&#xff0c;测试计划也会不断发生改变&a…...

教你如何为博客网站申请阿里云的免费域名HTTPS证书

如何为博客网站申请阿里云的免费域名HTTPS证书 文章目录 如何为博客网站申请阿里云的免费域名HTTPS证书前置条件&#xff1a;步骤1 例如阿里云控制台&#xff0c;选择SSL证书步骤2 申请购买免费证书步骤3 创建证书步骤3.1 证书申请步骤3.2 DNS域名验证 步骤4 等待证书审核成功&…...

在线Word怎么转换成PDF?Word无法转换成PDF文档原因分析

不同的文件格式使用方法是不一样的&#xff0c;而且也需要使用不同的工具才可以打开编辑内容&#xff0c;针对不同的场合用户们难免会用到各种各样的文件格式&#xff0c;要想在不修改内容的前提下提高工作效率&#xff0c;那就需要用到文件格式转换&#xff0c;那么在线Word怎…...

计算机网络:网络通信相关概念入门

目录 一、网络发展背景二、理解网络通信三、理解IP地址1.简述IP地址2.IP地址的版本3.提高地址利用率的技术 四、理解端口1.简述端口2.使用端口的原因 五、理解网络通信协议 一、网络发展背景 网络发展背景&#xff1a; 最初的计算机是单机&#xff0c;那么单机是这样传输数据的…...

Spring-2-透彻理解Spring 注解方式创建Bean--IOC

今日目标 学习使用XML配置第三方Bean 掌握纯注解开发定义Bean对象 掌握纯注解开发IOC模式 1. 第三方资源配置管理 说明&#xff1a;以管理DataSource连接池对象为例讲解第三方资源配置管理 1.1 XML管理Druid连接池(第三方Bean)对象【重点】 数据库准备 -- 创建数据库 create …...

LeetCode150道面试经典题--单词规律(简单)

1.题目 给定一种规律 pattern 和一个字符串 s &#xff0c;判断 s 是否遵循相同的规律。 这里的 遵循 指完全匹配&#xff0c;例如&#xff0c; pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。 2.示例 pattern"abba" s "c…...

uniapp把城市换成26个字母和城市排序

后端返回的数据 我们要得效果 <template><view><view v-for"(value,key) in cities" :key"key"><view style"color: red;"> {{ key }} </view><view style"border: 1rpx solid black;"><tex…...

Flv格式视频怎么转MP4?视频格式转换方法分享

FLV格式的视频是一种早期的视频格式&#xff0c;不支持更高的分辨率和比特率&#xff0c;这意味着视频的清晰度和质量受限制&#xff0c;无法很好地保留细节和质量&#xff0c;这种格式的视频已经逐渐被更高质量的视频格式所替代&#xff0c;例如MP4格式&#xff0c;不仅具有很…...

Java类与对象详解(3)

目录 封装 封装的概念 访问限定符 封装扩展之包 包的概念 导入包中的类 自定义包 基本规则 包的访问权限控制举例 常见的包 static 成员 static 修饰成员变量 static修饰成员方法 static 成员变量的初始化 代码块 代码块的概念及其分类 普通代码块 构造代码块…...

PMP备考指南来啦!

第一步&#xff1a;通读教材&#xff0c;了解学习内容 在正式开始课程的学习前&#xff0c;可以先快速简单地阅览一遍教材&#xff08;PMBOK&#xff09;&#xff0c;在较短的时间内知道自己将要学习的是什么内容&#xff1b;同时可以标记出难理解的知识点。这样做有以下两个好…...

计算机视觉中的特征检测和描述

一、说明 这篇文章是关于计算机视觉中特征检测和描述概念的简要理解。在其中&#xff0c;我们探讨了它们的定义、常用技术、简单的 python 实现和一些限制。 二、什么是特征检测和描述&#xff1f; 特征检测和描述是计算机视觉中的基本概念&#xff0c;在图像识别、对象跟踪和图…...

【docker】 运行bytetrack 构建映像失败 使用docker删除之前构建的映像

1 Docker删除docker build失败的images docker images | grep "<none>" | awk {print $3} | xargs docker rmi 2 Docker删除启动失败的image docker ps -a | awk {if (length($2) 12){print $1}} | xargs docker rm...

视图矩阵推导

线性代数知识背景 空间中对边向量相等的四边形是平行四边形 视图矩阵推导...

Linux | 隐藏终端并在指定路径下执行命令

文章目录 概述一、定义介绍二、操作教程(一)、编写脚本1.创建脚本2.编写代码(二)、执行脚本1.脚本执行2.自启动执行3.检查和杀死隐藏程序概述 本节详细介绍了如何在Ubuntu18系统下隐藏终端执行命令,同时可以指定命令执行路径。 一、定义介绍 隐藏终端启动其实很简单,只需要在…...

JavaSE_2.1——数组之Arrays工具类

Java提供了一个专门用于操作数组的工具类&#xff0c;即Arrays类&#xff0c;位于Java. util包下【需要导入】。该类提供了一系列方法来操作数组&#xff0c;例如排序、赋值、比较、填充数组 等&#xff0c;用户直接调用这些方法即可【例如&#xff1a;Arrays.sort(数组名)】&a…...

yolov5、YOLOv7、YOLOv8改进:注意力机制CA

目录 1.背景介绍 论文题目&#xff1a;《Coordinate Attention for Efficient Mobile NetWork Design》论文地址&#xff1a; https://arxiv.org/pdf/2103.02907.pdf 2.原理介绍 3.YOLOv5改进&#xff1a; 3.1common中加入下面代码 3.2在yolo.py中注册 3.3添加配置文件 …...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/

使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题&#xff1a;docker pull 失败 网络不同&#xff0c;需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

rnn判断string中第一次出现a的下标

# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...

Reasoning over Uncertain Text by Generative Large Language Models

https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...

JVM虚拟机:内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...

视觉slam十四讲实践部分记录——ch2、ch3

ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...

Java毕业设计:WML信息查询与后端信息发布系统开发

JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发&#xff0c;实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构&#xff0c;服务器端使用Java Servlet处理请求&#xff0c;数据库采用MySQL存储信息&#xff0…...

基于IDIG-GAN的小样本电机轴承故障诊断

目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) ​梯度归一化(Gradient Normalization)​​ (2) ​判别器梯度间隙正则化(Discriminator Gradient Gap Regularization)​​ (3) ​自注意力机制(Self-Attention)​​ 3. 完整损失函数 二…...