POJ 1979 Red and Black 深搜入门

2024-04-11 02:08
文章标签 入门 poj black red 1979

本文主要是介绍POJ 1979 Red and Black 深搜入门,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题意:给定一个 W*H 的矩形,“.”代表可到达的(黑色瓷片),“#”表示障碍(红色瓷片),某人在一个“@”的起始点,求他所能到达的瓷片有多少个(包括第一所占的瓷片)。

深度优先遍历图 VS 广度优先遍历图
深度优先遍历图 VS 广度优先遍历图.gif

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;public class Main {private static final int MAX_SIZE = 25;private static char tileColor[][] = new char[MAX_SIZE][MAX_SIZE];  // 瓷片的颜色private static boolean pass[][] = new boolean[MAX_SIZE][MAX_SIZE]; // 瓷片是否路过private static int blackNum;    // 能到达的黑色瓷片的数量private static void DFS(int indexI, int indexJ) {// 直到该瓷片都被访问if (pass[indexI][indexJ]) {return;}pass[indexI][indexJ] = true;// 标记已访问瓷片++blackNum;                 // 到达的瓷片加 1 // 向上走if (tileColor[indexI - 1][indexJ] != '#') {DFS(indexI - 1, indexJ);}// 向下走if (tileColor[indexI + 1][indexJ] != '#') {DFS(indexI + 1, indexJ);}// 向左走if (tileColor[indexI][indexJ - 1] != '#') {DFS(indexI, indexJ - 1);}// 向右走if (tileColor[indexI][indexJ + 1] != '#') {DFS(indexI, indexJ + 1);}}public static void main(String[] args) {Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));int H;  // 行int W;  // 列int indexC = 0;  // @ 所在的列int indexR = 0;  // @ 所在的行String inputStr;char temp;while (in.hasNext()) {W = in.nextInt();H = in.nextInt();if (H == 0 && W == 0) {break;}// 初始化,因为没墙包着,所以四周需要加墙for (int index = 0; index < MAX_SIZE; index++) {Arrays.fill(tileColor[index], '#');Arrays.fill(pass[index], false);}for (int indexI = 1; indexI <= H; indexI++) {inputStr = in.next();for (int indexJ = 1; indexJ <= W; indexJ++) {temp = inputStr.charAt(indexJ - 1);tileColor[indexI][indexJ] = temp;if (temp == '@') {indexC = indexJ;indexR = indexI;}}}blackNum = 0;  // 初始化DFS(indexR, indexC);out.println(blackNum);}out.flush();}
}

这篇关于POJ 1979 Red and Black 深搜入门的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

从入门到精通MySQL联合查询

《从入门到精通MySQL联合查询》:本文主要介绍从入门到精通MySQL联合查询,本文通过实例代码给大家介绍的非常详细,需要的朋友可以参考下... 目录摘要1. 多表联合查询时mysql内部原理2. 内连接3. 外连接4. 自连接5. 子查询6. 合并查询7. 插入查询结果摘要前面我们学习了数据库设计时要满

从入门到精通C++11 <chrono> 库特性

《从入门到精通C++11<chrono>库特性》chrono库是C++11中一个非常强大和实用的库,它为时间处理提供了丰富的功能和类型安全的接口,通过本文的介绍,我们了解了chrono库的基本概念... 目录一、引言1.1 为什么需要<chrono>库1.2<chrono>库的基本概念二、时间段(Durat

解析C++11 static_assert及与Boost库的关联从入门到精通

《解析C++11static_assert及与Boost库的关联从入门到精通》static_assert是C++中强大的编译时验证工具,它能够在编译阶段拦截不符合预期的类型或值,增强代码的健壮性,通... 目录一、背景知识:传统断言方法的局限性1.1 assert宏1.2 #error指令1.3 第三方解决

从入门到精通MySQL 数据库索引(实战案例)

《从入门到精通MySQL数据库索引(实战案例)》索引是数据库的目录,提升查询速度,主要类型包括BTree、Hash、全文、空间索引,需根据场景选择,建议用于高频查询、关联字段、排序等,避免重复率高或... 目录一、索引是什么?能干嘛?核心作用:二、索引的 4 种主要类型(附通俗例子)1. BTree 索引(

Redis 配置文件使用建议redis.conf 从入门到实战

《Redis配置文件使用建议redis.conf从入门到实战》Redis配置方式包括配置文件、命令行参数、运行时CONFIG命令,支持动态修改参数及持久化,常用项涉及端口、绑定、内存策略等,版本8... 目录一、Redis.conf 是什么?二、命令行方式传参(适用于测试)三、运行时动态修改配置(不重启服务

MySQL DQL从入门到精通

《MySQLDQL从入门到精通》通过DQL,我们可以从数据库中检索出所需的数据,进行各种复杂的数据分析和处理,本文将深入探讨MySQLDQL的各个方面,帮助你全面掌握这一重要技能,感兴趣的朋友跟随小... 目录一、DQL 基础:SELECT 语句入门二、数据过滤:WHERE 子句的使用三、结果排序:ORDE

Python中OpenCV与Matplotlib的图像操作入门指南

《Python中OpenCV与Matplotlib的图像操作入门指南》:本文主要介绍Python中OpenCV与Matplotlib的图像操作指南,本文通过实例代码给大家介绍的非常详细,对大家的学... 目录一、环境准备二、图像的基本操作1. 图像读取、显示与保存 使用OpenCV操作2. 像素级操作3.

POI从入门到实战轻松完成EasyExcel使用及Excel导入导出功能

《POI从入门到实战轻松完成EasyExcel使用及Excel导入导出功能》ApachePOI是一个流行的Java库,用于处理MicrosoftOffice格式文件,提供丰富API来创建、读取和修改O... 目录前言:Apache POIEasyPoiEasyExcel一、EasyExcel1.1、核心特性

Python中模块graphviz使用入门

《Python中模块graphviz使用入门》graphviz是一个用于创建和操作图形的Python库,本文主要介绍了Python中模块graphviz使用入门,具有一定的参考价值,感兴趣的可以了解一... 目录1.安装2. 基本用法2.1 输出图像格式2.2 图像style设置2.3 属性2.4 子图和聚

Spring Boot + MyBatis Plus 高效开发实战从入门到进阶优化(推荐)

《SpringBoot+MyBatisPlus高效开发实战从入门到进阶优化(推荐)》本文将详细介绍SpringBoot+MyBatisPlus的完整开发流程,并深入剖析分页查询、批量操作、动... 目录Spring Boot + MyBATis Plus 高效开发实战:从入门到进阶优化1. MyBatis