week4 搜索

这篇具有很好参考价值的文章主要介绍了week4 搜索。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、 迷宫

1.题目描述

给定一个 N × M N \times M N×M 方格的迷宫,迷宫里有 T T T 处障碍,障碍处不可通过。

在迷宫中移动有上下左右四种方式,每次只能移动一个方格。数据保证起点上没有障碍。

给定起点坐标和终点坐标,每个方格最多经过一次,问有多少种从起点坐标到终点坐标的方案。

2.输入格式

第一行为三个正整数 N , M , T N,M,T N,M,T,分别表示迷宫的长宽和障碍总数。

第二行为四个正整数 S X , S Y , F X , F Y SX,SY,FX,FY SX,SY,FX,FY S X , S Y SX,SY SX,SY 代表起点坐标, F X , F Y FX,FY FX,FY 代表终点坐标。

接下来 T T T 行,每行两个正整数,表示障碍点的坐标。

3.输出格式

输出从起点坐标到终点坐标的方案总数。

样例 #1

样例输入 #1

2 2 1
1 1 2 2
1 2

样例输出 #1

1

4.思路

用一个数组记忆障碍所在位置和之前遍历时是否经过,若在一次遍历中结果是能到达终点则sum++。

5.代码

#include<bits/stdc++.h>
using namespace std;
int n,m,t,sx,fx,sy,fy;
int sum;
int a[6][6];
bool vis[6][6];
int xx[5]={-1,0,1,0}; 
int yy[5]={0,1,0,-1}; 
void dfs(int x,int y){
	int next_x,next_y;
	if(x==fx&&y==fy){
		sum++;
		return ;
	}
	for(int i=0;i<=3;i++){
		next_x=x+xx[i];
		next_y=y+yy[i];
		if(next_x>=1&&next_x<=n&&next_y>=1&&next_y<=m&&vis[next_x][next_y]==false){
			vis[next_x][next_y]=true;
			dfs(next_x,next_y);
			vis[next_x][next_y]=false;
		}
	}
}
int main(){
	cin>>n>>m>>t;
	cin>>sx>>sy>>fx>>fy;
	for(int i=1;i<=t;i++){
		int x,y;cin>>x>>y;
		vis[x][y]=true;
	}
	vis[sx][sy]=true;
	dfs(sx,sy);
	cout<<sum;
	return 0; 
}

二、马的遍历

1.题目描述

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

2.输入格式

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

3.输出格式

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

样例 #1

样例输入 #1

3 3 1 1

样例输出 #1

0    3    2    
3    -1   1    
2    1    4

4.思路

将每次马能走到的八个位置求出,再进行判断能不能到达,经过的地点用数组记忆下次不再经过。若遍历一趟后没过某一点,此点变为一(直接一开始全部将数组初始化为-1).文章来源地址https://www.toymoban.com/news/detail-412816.html

5.代码

#include<bits/stdc++.h>
using namespace std;
int n,m,hx,hy,sum=0;
queue<pair<int ,int> >q;
int a[500][500];
bool vis[500][500];
int xx[8]={-2,-2,2,2,-1,-1,1,1};
int yy[8]={-1,1,-1,1,-2,2,-2,2};
int main(){
	cin>>n>>m>>hx>>hy;int sum=5;
	memset(a,-1,sizeof(a));
	vis[hx][hy]=1;a[hx][hy]=0;
	q.push(make_pair(hx,hy));
	while(!q.empty()){
		int x=q.front().first;
		int y=q.front().second;
		q.pop();
		for(int i=0;i<=7;i++){
			int x2=x+xx[i];
			int y2=y+yy[i];
			if(x2>=1&&x2<=n&&y2>=1&&y2<=m&&vis[x2][y2]==false){
				vis[x2][y2]=true;
				q.push(make_pair(x2,y2));
				a[x2][y2]=a[x][y]+1;
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cout<<a[i][j]<<" ";
		}
		cout<<endl;
	}
	return 0;
}

到了这里,关于week4 搜索的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • NewStarCTF 2023 公开赛道 WEEK4|CRYPTO 部分WP

    1、题目信息 提示: \\\"Schmidt Samoa\\\" 附件信息 2、解题方法 学了一个新技巧,哈哈哈。 简介 : Schmidt-Samoa密码系统,像rabin加密一样,其安全性基于整数因式分解的难度。但 Rabin 解密时会得到四个解,而 Schmidt-Samor 得到的是唯一解。 密钥生成 1.选取两个大的质数p和q并进行计算

    2024年02月08日
    浏览(45)
  • [BUUCTF NewStarCTF 2023 公开赛道] week4 crypto/pwn

    再补完这个就基本上完了. Schmidt-Samoa密码系统看上去很像RSA,其中N=pqq, 给的e=N给了d NTRU又一个格的基本应用   当E.order() == p时   p-1光滑时的分解 此题先是p-1光滑分解,然后是e=3*0x10000先求3次根再用rabin求16次    求误差,虽然被分成3个数组,但本质上是一个,可以连到一起求解. 

    2024年02月07日
    浏览(38)
  • 剑指offer题解合集——Week4day2

    题目链接:二叉树中和为某一值的路径 AC代码 思路: 整体思路

    2024年01月15日
    浏览(46)
  • 前端架构师-week4-脚手架命令注册和执行过程开发

    基于 Commander 完成脚手架命令注册和命令执行过程开发 ·如何设计高性能脚手架(缓存 + 多进程 实现这一点) ·Node 多进程开发 ·javascript 面向对象的实战技巧(达到可扩展 高复用) ·图解高性能脚手架架构设计方法 ·封装通用的 Package 和 Command 类 ·基于缓存 + Node 多进程实现

    2024年02月01日
    浏览(56)
  • 前端架构师-week4-封装通用的npm包管理类Package

    目录 脚手架命令本地调试功能支持 动态执行库exec模块创建 创建 npm 模块通用类 Package Package 类的属性、方法定义及构造函数逻辑开发 Package 类获取入口文件路径功能开发(pkg-dir应用+解决不同操作系统路径兼容问题)  利用 npminstall 库安装 npm 模块 Package 类判断模块是否存在

    2024年02月03日
    浏览(42)
  • 【北邮国院大三下】Cybersecurity Law 网络安全法 Week4

    北邮国院大三电商在读,随课程进行整理知识点。仅整理PPT中相对重要的知识点,内容驳杂并不做期末突击复习用。个人认为相对不重要的细小的知识点不列在其中。如有错误请指出。转载请注明出处,祝您学习愉快。 编辑软件为Effie,如需要pdf/docx/effiesheet/markdown格式的文件

    2024年02月11日
    浏览(74)
  • NEUQ-acm第二期训练Week4——代码源div2

    RSA算法选择两个不同质数的积作为模数。现在有两个正整数 A,B,如果它们是不同的质数,则判定为 full credit;否则,如果A⋅B不是任意大于1的整数的平方的整数倍,则判定 partial credit;否则判定为no credit。 一行两个正整数 A,B。 full credit 或 partial credit 或 no credit。 数据规模

    2024年02月16日
    浏览(36)
  • NewStarCTF2023week4-midsql(利用二分查找实现时间盲注攻击)

    大致测试一下,发现空格被过滤了 使用内联注释/**/绕过,可行 使用%a0替代空格,也可以  再次测试发现等号也被过滤,我们使用 like 代替 (我最开始以为是and被过滤,并没有,如果是and或者or被过滤我们也可以使用 和 || 替代) 但是这里尝试了很多都只返回一个页面,没有

    2024年02月07日
    浏览(47)
  • 某软件的一个模块的需求规格说明书中描述【软件测试题目】

    某软件的一个模块的需求规格说明书中描述 (1)年薪制员工:严重过失,扣年终风险金的4%;过失,扣年终风险金的2% (2)非年薪制员工:严重过失,扣除当月薪资的8%;过失,扣除当月薪资的4% (1)分析原因及结果 原因 c1:年薪制员工 c2:非年薪制员工 c3:过失 c4:严重过失

    2024年02月08日
    浏览(50)
  • 题目:2185.统计包含给定前缀的字符串

    ​​ 题目来源:         leetcode题目,网址:2185. 统计包含给定前缀的字符串 - 力扣(LeetCode) 解题思路:        遍历判断即可。 解题代码: 总结:         官方题解也是一样的思路。

    2024年02月15日
    浏览(69)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包