360笔试题2013

2023-05-16


编程题、传教士人数M,野人C,M≥C,开始都在岸左边,
①船只能载两人,传教士和野人都会划船,当然必须有人划船
②两岸边保证野人人数不能大于传教士人数   
把所有人都送过河,设计一方案,要求编程实现。 


思路:

深度搜索。

状态:左岸和右岸的人数+船的位置。

每一个状态下,会有5种状态可以转移,

即:

1,运送2个传教士到对岸;

2,运送2个野人到对岸;

3,运送1个传教士到对岸;

4,运送1个野人到对岸;

5,运送1个传教士和一个野人到对岸。


从初始状态开始搜,搜索这五种情况,

进入下一状态,判断该状态是否满足条件,

即两岸野人的个数是否比该岸的传教士多,

如果满足条件,则继续搜索该状态下的五种情况。

深度搜索下去,直到找到最后的解。


注意:

1,如果搜索的状态在之前已经出现过了,就不深入下去了,

否则会出现死循环,比如运两个野人过去,再运回来,状态复原了,

如果一直这么搜下去,就没玩没了了。

2,状态包括船的信息,如果两边的人数都是一样,但是船的位置不一样,

那么这是两种状态。

3,要搜索的目标状态是人都在对岸且船在对岸。


PS:

当M=C>3时,没有解。

当M>C时,有解。


#include <iostream>
#include <vector>
#include <string>
#include <stdio.h>
using namespace std;

bool flag = true; //true:表示在右岸
vector<string> visit; //记录已经访问过的状态

bool dfs( int M, int C, int m, int c){
	if( M<0||C<0||m<0||c<0)   //非法
		return false;
	if( (M&&C>M) ||(m&&c>m))   //野人会吃牧师
		return false;
	
	if( flag&&M==0&&C==0 ||(!flag&&m==0&&c==0))  //全部运输过去
		return true;

	//检查该节点是否出现过
	char s[30];
	if( !flag )
		sprintf( s, "M=%d,C=%d,m=%d,c=%d,boat=left", M,C,m,c);
	else
		sprintf( s, "M=%d,C=%d,m=%d,c=%d,boat=right", m,c,M,C);
	string str(s);
	for( int i=0; i<visit.size(); i++)
		if( visit[i]==str)                     //该状态已经搜索过了
			return false;

	visit.push_back(str);
	flag = !flag;
	if( dfs( m+2, c, M-2,C) ){
		printf("2,0\n");
		printf("%s\n",s);
		return true;
	}
	else if( dfs( m, c+2, M, C-2) ){
		printf("0,2\n");
		printf("%s\n",s);
		return true;
	}
	else if( dfs( m+1, c+1, M-1, C-1) ){
		printf("1,1\n");
		printf("%s\n",s);
		return true;
	}
	else if( dfs( m+1, c, M-1, C)){
		printf("1,0\n");
		printf("%s\n",s);
		return true;
	}
	else if( dfs( m, c+1, M, C-1)){
		printf("0,1\n");
		printf("%s\n",s);
		return true;
	}
	flag = !flag;
	visit.pop_back();
	return false;
}

int main(){
	char s[30];
	int M=6,C=6,m=0,c=0;
	sprintf( s, "M=%d,C=%d,m=%d,c=%d,boat=left", M,C,m,c);
	printf("%s\n",s);
	if(!dfs(M,C,0,0))
		cout << "Can not find the solution."<<endl;
	return 0;
}




本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

360笔试题2013 的相关文章

  • delete释放new[] 以及 delete[]释放new 的问题

    在同花顺 的笔试过程中遇到这么一个类似问题 A ptr 61 new A 10 for int i 61 0 i lt n i 43 43 delete amp ptr i 由此衍生出两个问题 new 申请的空间用delete释放会发生什么
  • C#中的readonly与const区别

    xfeff xfeff const 的概念就是一个包含不能修改的值的变量 常数表达式是在编译时可被完全计算的表达式 因此不能从一个变量中提取的值来初始化常量 如果 const int a 61 b 43 1 b是一个变量 xff0c 显然不
  • 改变无线连接、有线连接的优先级

    有线和无线连的是同一个网络 xff0c 当笔记本打开时 xff0c 总是优先使用无线连接 xff0c 如何转变优先级为有线连接呢 xff1f 1 打开网络和共享中心 2 更改适配器设置 xff0c 打开网络连接窗口 3 单击此窗口的高级菜单
  • 杂感一

    从2014年7月工作至今已有快2年了 xff0c csdn的博客从毕业后就很少上了 工作中有很多收获 技术上 也在不断积累和成长中 不管做什么事情 xff0c 要坚持下去 xff0c 方得初心 xff0c 把坚持养成习惯 xff0c 学习如
  • Kotlin实战---Retrofit网络模型

    没有Kotlin基础的小伙伴先进这里 Koltin基础文章 1 Java和Kotlin互相调用之间的注意事项 1 解决关键字冲突 span class token keyword public span span class token k
  • MFC隐藏主窗口的方法

    隐藏基于对话框的MFC应用程序窗口的方法 推荐这个方法 xff0c 非常好用 很多人可能会将窗口创建出来 然后用一个 ShowWindow SW HIDE 的方法去隐藏窗口 当然这是可以做到隐藏的功能 但是有一点不足的地方就是窗口在隐藏之前
  • JSP 通过Servlet将excel数据导入SQL

    1 gt 在网上下载jxl jar 这个JAR包用于Java操作excel 下载后 xff0c 将这个包复制到工程Webroot下的WEB INF下的lib中 xff0c 或是在工程中导入jxl jar包 2 gt 准备excel文件 如图
  • 1=5,2=15,3=215,4=2145,那么5=?

    如题 xff0c 1 61 5 xff0c 2 61 15 xff0c 3 61 215 xff0c 4 61 2145 xff0c 那么5 61 xff1f 答案 xff1a 5 61 1 哎 xff0c 这个题出的 xff0c 没反应过
  • 村子里有50个人,每人有一条狗,在这50条狗中有病狗(这种病不传染),于是人们要找出病狗。

    xff29 xff22 xff2d 公司向来以高素质人才作为企业持续竞争力的保证 进入 xff29 xff22 xff2d 公司是差不多每个 xff29 xff34 人的梦想 下面这条 xff29 xff22 xff2d 公司的面试题 xf
  • 删除单向链表中的某一个节点

    已知一个单向链表的表头head xff0c 写出一个删除某一个节点的算法 xff0c 要求先找到此节点 xff0c 然后删除 include lt iostream gt using namespace std typedef struct
  • 多段图的最短路径问题-----动态规划法

    对多段图 xff0c 求最短路径 xff0c 如图 xff1a 对其使用动态规划法 xff1a 阶段 xff1a 将图中的顶点划分5个阶段 xff0c k 状态 xff1a 每个阶段有几种供选择的点s 决策 xff1a 当前状态应在前一个状
  • Android 文件存储 和 权限管理

    转载请标明出处 xff1a xff1a http blog csdn net huaiyiheyuan article details 52473984 android SD卡主要有两种存储方式 Internal External Stor
  • Python 连接Linux服务器完成上传下载和执行命令及查询目录下的文件

    Python 连接Linux服务器完成上传下载和执行命令及查询目录下的文件 记录一些用于连接linux获取远端文件或者上传文件的小工具 xff0c 另外还有执行shell命令和查找linux目录下文件是否存在 span class toke
  • 【学习整理】Windows server 2019AD域之创建用户的三种形式

    内置工具程序csvde exe xff0c ldifde exe dsadd exe csvde exe xff1a 能利用它来新建用户账户 xff0c 但不能修改 需要将用户数据输入纯文本文件中ldifde exe xff1a 可以利用它
  • 邮件退信提示

    一般情况下 xff0c 当您发送的邮件无法正常到达收件人时 xff0c winmail 邮件系统将会自动给您发一封系统退信 xff0c 这封退信通知里面包含了无法正常发送到对方邮件地址的原因 xff0c 所以绝大多数情况下可以通过退信通知来
  • 学以致用--注解加反射实现Butterknife的View注入功能

    不知不觉更文挑战来到了第三天 xff0c 今天来写一篇反射和注解的应用篇 对反射不熟悉的同学 xff0c 请阅读 搞懂Java反射和JDK里的动态代理 对注解不熟悉的同学 xff0c 请阅读 搞懂Java高级特性 注解 首先这篇文章 xff
  • 百度试题---开发测试工程师

    一 问答题 说出常用的几种希哈函数 xff0c 其作用是什么 xff1f 描述OSI 的七层网络结构 xff0c HTTP 工作在哪一层 xff1f 描述一段C 语言代码程序能运行起来的代码要求和执行过程 二 算法设计 有一车苹果 xff0
  • 错误: Entry在LinkedHashMap中不是公共的; 无法从外部程序包中对其进行访问

    遇到了一个很奇怪的问题 xff0c 使用LinkedHashMap来做LRU缓存时 xff0c 重写protected boolean removeEldestEntry Entry lt String String gt eldest 方
  • 【安卓真机调试】较全面的Android真机调试详解

    目录 1 启动调试功能1 1 配置设备上的开发者选项1 2 运行可调试的 build 变体 2 开始调试2 1 设置断点2 2 选择设备2 3 在工具栏中点击Debug图标2 4 打开Debug窗口2 5 将调试程序连接到正在运行的应用上
  • 如何搭建ftp服务器实现文件共享

    这里以windows系统和linux系统为例 xff0c 简单介绍一下如何在这2种系统下搭建ftp服务器 xff0c 整个过程非常简单 xff0c 感兴趣的朋友可以自己尝试一下 xff1a windows windows系统自带有ftp服务

随机推荐

  • Rabbitmq—— 从入门到放弃

    文章目录 背景总体架构类与方法BlockingConnection init channel BlockingChannelqueue declarequeue deleteexchange declarebasic publishbasi
  • 使用electron-vue+go写一个处理excel表格小软件(2)

    目录 问题思路go部分主要流程遇到的坑 node部分主要流程遇到的坑 源码链接 问题 使用node xlsx处理excel一次最多能处理30M的文件 xff0c 所以来个80M的话就要手动拆成3个文件 xff0c 这看起来太蠢了 xff0c
  • Gradle project sync failed的解决方法

    开发工具android studio在运行项目的时候报如下错误 xff1a Error Gradle project sync failed Please fix your project and try again 编辑gradle wr
  • Mvp契约类实践

    MVP中关于契约的用法 契约类的好处 xff1a 低耦合 接口统一管理 业务逻辑清晰 易于后期维护 以最简单的登录为例 xff1a loginContract契约类 span class token comment 契约类 span spa
  • Ubuntu Wine deepin-Wechat生成方法

    转自https ywnz com linuxjc 5530 html 更新deepin中微信的方法 1 下载官方打包的xxx deb xff0c 放至 xff5e wine app文件夹中 2 创建文件夹extract xff0c 并在ex
  • 借助Redis Bitmap实现简单的布隆过滤器

    在之前的一篇文章中 xff0c 我们已经深入理解了布隆过滤器的基本原理 xff0c 并且了解到它在缓存系统中有较多的应用 Redis提供的Bitmap正好能够作为布隆过滤器所需要的位数组的基础 xff0c 本文先简要介绍Bitmap xff
  • AndroidStudio编写编译脚本Gradle文件时没有,没有代码提示,ctrl + 点击属性时提示Cannot find declaration to go to

    问题描述 AndroidStudio编写编译脚本Gradle文件时没有 xff0c 没有代码提示 xff0c ctrl 43 点击属性时提示Cannot find declaration to go to 原因分析 xff1a gradle
  • 在Ubuntu下最靠谱的键位修改方法 ,亲测有效

    本人刚入坑linux不久 我一直在windows下工作 同样linux我也当成windows来玩 也常有改键位的需求 我曾经百度无数改键位的方法 要么就是只能改左边的ctrol和大小写键交换 右边的alt和ctrol交换失败 有的教程能交换
  • svn怎么切换分支

    项目场景 xff1a svn切换不成功 问题描述 怎么切换都不成功 原因分析 xff1a 解决方案 xff1a 1查看当前所在的位置 2点击switch 3to path选中需要的路径 xff0c ok就可以了 重复1步骤就能查看当前路径是
  • android studio识别不到夜神模拟器怎么办

    问题描述 xff1a 正常运行情况下 xff0c 夜神模拟器突然找不到了 xff1b 解决方案 xff1a 1 找到夜神模拟器的目录bin目录下 xff0c 路径栏中输入cmd回车 xff0c 进入控制台页面 2 执行命令 nox adb
  • Android 动态设置padding跟margin的问题

    padding view setPadding int left int top int right int bottom margin LayoutParams lp 61 LayoutParams view getLayoutParam
  • svn如何合并代码

    1 先提交本地代码 2 切换至要汇总代码的目标枝干 3 在目标枝干选择最外层的文件夹 xff0c 然后右击文件夹 merge 4 选择需要合并的分支 xff0c 和需要合并的日志 xff1b 5可以先test merge xff0c 然后选
  • android studio logcat 无日志 No connect devices

    解决 xff1a 去sdk tools中找到 google use driver xff0c 下载 xff0c 然后重启编译器 成功 连接不上夜神模拟器可以去夜神对应的bin目录下 xff0c 在目录框中输入cmd回车 输入nox adb
  • android findviewbyid 返回null

    findViewById返回Null 转自 xff1a http blog sina com cn s blog 5e58565701012q2d html 错误 xff1a findViewById返回Null xff0c 报nullpo
  • nox夜神模拟器连接不上android studio,用bat脚本快速输入命令

    不知道为什么android studio老是会识别不到夜神模拟器 xff1b 之前都是通过cmd 到夜神的bin目录下面 然后输入命令 xff0c 连接模拟器 现在发现一种更简单的做法 xff1b 1 创建一个文本文档 xff0c 改名的时
  • 微策略2017年秋招线下笔试+技术面+在线测评+主管面总结

    1 前言 微策略可能在国内的知名度比较小 xff0c 它是一家总部在美国 xff0c 在杭州设立研发中心 xff0c 主要做智能商用软件的外企 更多的信息 xff0c 请自行搜索 我是17年10月份面试微策略 xff0c 然后拿到的开发 x
  • Gradle Wrapper是什么

    Gradle提供了内置的Wrapper task帮助我们自动生成Wrapper所需要的目录文件 在一个项目中的根目录下执行 gradle wrapper即可生成 工程结构介绍 xff1a gradlew xff1a Linux下的可执行脚本
  • nginx上传文件失败,提示上传文件过大,怎么解决

    问题描述 xff1a 上传文件失败 xff0c 文件大小4M左右 上传程序为Java xff0c 通过nginx反向代理写入Fastdfs中 xff0c 但是一直失败 xff0c 查看nginx错误日志 xff0c 提示如下内容 xff1a
  • slf4j,log4j,logback之间的关系

    1 SLF4J Simple logging Facade for Java 意思为简单日志门面 xff0c 它是把不同的日志系统的实现进行了具体的抽象化 xff0c 只提供了统一的日志使用接口 xff0c 使用时只需要按照其提供的接口方法
  • 360笔试题2013

    编程题 传教士人数M xff0c 野人C xff0c M C xff0c 开始都在岸左边 xff0c 船只能载两人 xff0c 传教士和野人都会划船 xff0c 当然必须有人划船 两岸边保证野人人数不能大于传教士人数 把所有人都送过河 xf