【OJ】1086: 地砖问题

2024-02-10 02:30
文章标签 问题 oj 地砖 1086

本文主要是介绍【OJ】1086: 地砖问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

这个问题在理解了BFS算法之后就能很快的写出了,个人感觉BFS和DFS就是状态之间的转换,就是从一个状态转移到另外一个状态,所以我首先定义好了状态,具体的事宜且见下面的代码:

#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;// 定义状态
struct Status {int x;int y;
};// 保存地图
char map[25][25];// 标志地图中的每个点是否被访问过 如果访问过则为true
bool mark[25][25];// 四个方向 ----> 上下左右
int go[][2] = {1,0,-1,0,0,1,0,-1
};queue<Status>Q;bool check(int x, int y,int H,int W) {// 检查位置(x,y) 是否可以访问if (x<1 || x>H || y<1 || y>W || mark[x][y] == true || map[x][y] == '#') {return false;}return true;
}// 使用引用来保存答案
void BFS(int &ret, int H, int W)
{while (!Q.empty()) {Status cur = Q.front();Q.pop();ret++;for (int i = 0; i < 4; i++) {// 得到当前位置的下一个位置  有四种可能 即上下左右 int nx = cur.x + go[i][0];// 下一个位置的x坐标int ny = cur.y + go[i][1];// 下一个位置的y坐标Status t;// 生成新的状态t.x = nx;t.y = ny;if (check(nx, ny, H, W)) {// 如果新的状态符合要求   就入队  Q.push(t);mark[nx][ny] = true;  // 标记为已经访问过}}}
}int main()
{int W, H;while (scanf("%d%d", &W, &H) != EOF) {getchar();//干掉输入W、H后的那个回车if (W == 0 && H == 0)break;// 清空上一次的输入for (int i = 0; i < 25; i++) {for (int j = 0; j < 25; j++) {mark[i][j] = false;map[i][j] = 0;}}while (!Q.empty()) {Q.pop();}// 进入本次输入for (int i = 1; i <= H; i++) {// 按照每一行直接输进去scanf("%s", map[i] + 1);// 注意这里的%s    map[i]+1}// 初始化Status head;for (int i = 1; i <= H; i++) {for (int j = 1; j <= W; j++) {if (map[i][j] == '@') {head.x = i;head.y = j;mark[i][j] = true;}}}Q.push(head);// ret用来保存答案int ret = 0;// 调用BFS函数BFS(ret, H, W);printf("%d\n", ret);}return 0;
}

路漫漫其修远兮,吾将上下而求索!

这篇关于【OJ】1086: 地砖问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:https://blog.csdn.net/CholenMine/article/details/83182542
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/695911

相关文章

Flask解决指定端口无法生效问题

《Flask解决指定端口无法生效问题》文章讲述了在使用PyCharm开发Flask应用时,启动地址与手动指定的IP端口不一致的问题,通过修改PyCharm的运行配置,将Flask项目的运行模式从Fla... 目录android问题重现解决方案问题重现手动指定的IP端口是app.run(host='0.0.

Seata之分布式事务问题及解决方案

《Seata之分布式事务问题及解决方案》:本文主要介绍Seata之分布式事务问题及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Seata–分布式事务解决方案简介同类产品对比环境搭建1.微服务2.SQL3.seata-server4.微服务配置事务模式1

mysql关联查询速度慢的问题及解决

《mysql关联查询速度慢的问题及解决》:本文主要介绍mysql关联查询速度慢的问题及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录mysql关联查询速度慢1. 记录原因1.1 在一次线上的服务中1.2 最终发现2. 解决方案3. 具体操作总结mysql

一文教你解决Python不支持中文路径的问题

《一文教你解决Python不支持中文路径的问题》Python是一种广泛使用的高级编程语言,然而在处理包含中文字符的文件路径时,Python有时会表现出一些不友好的行为,下面小编就来为大家介绍一下具体的... 目录问题背景解决方案1. 设置正确的文件编码2. 使用pathlib模块3. 转换路径为Unicod

Spring MVC跨域问题及解决

《SpringMVC跨域问题及解决》:本文主要介绍SpringMVC跨域问题及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录跨域问题不同的域同源策略解决方法1.CORS2.jsONP3.局部解决方案4.全局解决方法总结跨域问题不同的域协议、域名、端口

SpringBoot自定义注解如何解决公共字段填充问题

《SpringBoot自定义注解如何解决公共字段填充问题》本文介绍了在系统开发中,如何使用AOP切面编程实现公共字段自动填充的功能,从而简化代码,通过自定义注解和切面类,可以统一处理创建时间和修改时间... 目录1.1 问题分析1.2 实现思路1.3 代码开发1.3.1 步骤一1.3.2 步骤二1.3.3

基于.NET编写工具类解决JSON乱码问题

《基于.NET编写工具类解决JSON乱码问题》在开发过程中,我们经常会遇到JSON数据处理的问题,尤其是在数据传输和解析过程中,很容易出现编码错误导致的乱码问题,下面我们就来编写一个.NET工具类来解... 目录问题背景核心原理工具类实现使用示例总结在开发过程中,我们经常会遇到jsON数据处理的问题,尤其是

springboot3.4和mybatis plus的版本问题的解决

《springboot3.4和mybatisplus的版本问题的解决》本文主要介绍了springboot3.4和mybatisplus的版本问题的解决,主要由于SpringBoot3.4与MyBat... 报错1:spring-boot-starter/3.4.0/spring-boot-starter-

在 Spring Boot 中使用异步线程时的 HttpServletRequest 复用问题记录

《在SpringBoot中使用异步线程时的HttpServletRequest复用问题记录》文章讨论了在SpringBoot中使用异步线程时,由于HttpServletRequest复用导致... 目录一、问题描述:异步线程操作导致请求复用时 Cookie 解析失败1. 场景背景2. 问题根源二、问题详细分

解读为什么@Autowired在属性上被警告,在setter方法上不被警告问题

《解读为什么@Autowired在属性上被警告,在setter方法上不被警告问题》在Spring开发中,@Autowired注解常用于实现依赖注入,它可以应用于类的属性、构造器或setter方法上,然... 目录1. 为什么 @Autowired 在属性上被警告?1.1 隐式依赖注入1.2 IDE 的警告: