洛谷 P1141 01迷宫 (dfs解决)

2024-06-21 21:12
文章标签 解决 01 dfs 洛谷 迷宫 p1141

本文主要是介绍洛谷 P1141 01迷宫 (dfs解决),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

有一个仅由数字 0 与 1 组成的 n×n 格迷宫。若你位于一格 0 上,那么你可以移动到相邻 4 格中的某一格 1 上,同样若你位于一格 1 上,那么你可以移动到相邻 4 格中的某一格 0 上。

你的任务是:对于给定的迷宫,询问从某一格开始能移动到多少个格子(包含自身)。

输入格式

第一行为两个正整数 𝑛,𝑚。

下面 𝑛 行,每行 𝑛 个字符,字符只可能是 0 或者 1,字符之间没有空格。

接下来 𝑚 行,每行两个用空格分隔的正整数 𝑖,𝑗,对应了迷宫中第 𝑖 行第 𝑗 列的一个格子,询问从这一格开始能移动到多少格。

输出格式

𝑚 行,对于每个询问输出相应答案。

这道题最优解是并查集,把这些01分块每个坐标的块所能达到的最大面积就是该坐标的答案,这里我们讲讲用dfs如何解决这个问题:

首先他的条件是这个格子是0那你只能上下左右移动,并且下一个格子必须是1(反之相反),那么这个地方就是这道题的坑点了,如果没有这个限制,这个题基本就是dfs的模板题目了,那有了这个限制就需要一些小技巧:

我们发现迷宫都是01组成的,在c++程序中你会发现如果a = 1,那么!a = 0,那么可以利用这个点,在每次搜索是都传入上一个点迷宫的"!值",这样一来只用判断这个点是否与他相等即可,代码如下:

#include <bits/stdc++.h>
using namespace std;int b[1005][1005],arr[100005];
char s[1005][1005];
int n,m;void dfs(int i,int j,int k,int index){if(i < 0 || i >= n || j < 0 || j >= n || b[i][j] != -1 || k != s[i][j] - '0') return;b[i][j] = index;arr[index] ++;dfs(i - 1,j,!k,index);dfs(i + 1,j,!k,index);dfs(i,j - 1,!k,index);dfs(i,j + 1,!k,index);
}int main()
{cin >> n >> m;memset(b,-1,sizeof(b));for(int i=0;i<n;i++){cin >> s[i];}for(int i=0,x,y;i<m;i++){cin >> x >> y;x --, y --;if(b[x][y] == -1) dfs(x,y,s[x][y] - '0',i);else arr[i] = arr[b[x][y]];}for(int i=0;i<m;i++){cout << arr[i] << endl;}return 0;
}

加油

这篇关于洛谷 P1141 01迷宫 (dfs解决)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1082348

相关文章

SQL Server配置管理器无法打开的四种解决方法

《SQLServer配置管理器无法打开的四种解决方法》本文总结了SQLServer配置管理器无法打开的四种解决方法,文中通过图文示例介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录方法一:桌面图标进入方法二:运行窗口进入检查版本号对照表php方法三:查找文件路径方法四:检查 S

Redis出现中文乱码的问题及解决

《Redis出现中文乱码的问题及解决》:本文主要介绍Redis出现中文乱码的问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 问题的产生2China编程. 问题的解决redihttp://www.chinasem.cns数据进制问题的解决中文乱码问题解决总结

Python中Tensorflow无法调用GPU问题的解决方法

《Python中Tensorflow无法调用GPU问题的解决方法》文章详解如何解决TensorFlow在Windows无法识别GPU的问题,需降级至2.10版本,安装匹配CUDA11.2和cuDNN... 当用以下代码查看GPU数量时,gpuspython返回的是一个空列表,说明tensorflow没有找到

解决未解析的依赖项:‘net.sf.json-lib:json-lib:jar:2.4‘问题

《解决未解析的依赖项:‘net.sf.json-lib:json-lib:jar:2.4‘问题》:本文主要介绍解决未解析的依赖项:‘net.sf.json-lib:json-lib:jar:2.4... 目录未解析的依赖项:‘net.sf.json-lib:json-lib:jar:2.4‘打开pom.XM

XML重复查询一条Sql语句的解决方法

《XML重复查询一条Sql语句的解决方法》文章分析了XML重复查询与日志失效问题,指出因DTO缺少@Data注解导致日志无法格式化、空指针风险及参数穿透,进而引发性能灾难,解决方案为在Controll... 目录一、核心问题:从SQL重复执行到日志失效二、根因剖析:DTO断裂引发的级联故障三、解决方案:修复

IDEA Maven提示:未解析的依赖项的问题及解决

《IDEAMaven提示:未解析的依赖项的问题及解决》:本文主要介绍IDEAMaven提示:未解析的依赖项的问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝... 目录IDEA Maven提示:未解析的依编程赖项例如总结IDEA Maven提示:未解析的依赖项例如

解决Entity Framework中自增主键的问题

《解决EntityFramework中自增主键的问题》:本文主要介绍解决EntityFramework中自增主键的问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝... 目录Entity Framework中自增主键问题解决办法1解决办法2解决办法3总结Entity Fram

Nginx 配置跨域的实现及常见问题解决

《Nginx配置跨域的实现及常见问题解决》本文主要介绍了Nginx配置跨域的实现及常见问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来... 目录1. 跨域1.1 同源策略1.2 跨域资源共享(CORS)2. Nginx 配置跨域的场景2.1

qt5cored.dll报错怎么解决? 电脑qt5cored.dll文件丢失修复技巧

《qt5cored.dll报错怎么解决?电脑qt5cored.dll文件丢失修复技巧》在进行软件安装或运行程序时,有时会遇到由于找不到qt5core.dll,无法继续执行代码,这个问题可能是由于该文... 遇到qt5cored.dll文件错误时,可能会导致基于 Qt 开发的应用程序无法正常运行或启动。这种错

SpringBoot排查和解决JSON解析错误(400 Bad Request)的方法

《SpringBoot排查和解决JSON解析错误(400BadRequest)的方法》在开发SpringBootRESTfulAPI时,客户端与服务端的数据交互通常使用JSON格式,然而,JSON... 目录问题背景1. 问题描述2. 错误分析解决方案1. 手动重新输入jsON2. 使用工具清理JSON3.