java红与黑算法,AcWing 1113. 红与黑——Java宽搜版代码

布满荆棘的人生 2023-01-13 10:11 11阅读 0赞

import java.io.\*;

import java.util.\*;

public class Main \{

public static void main(String\[\] args) throws IOException \{

BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

String\[\] temp = reader.readLine().split(" ");

ArrayList result = new ArrayList<>();

class Pair\{

int x;

int y;

public Pair(int x, int y) \{

this.x = x;

this.y = y;

\}

\}

while(true)\{

int w = Integer.parseInt(temp\[0\]), h = Integer.parseInt(temp\[1\]);

//这里为方便边界处理，多声明一圈的区域

/\*

例： 0表示不使用的空间，\*表示实际使用的空间，当前需要使用2x3的区域

0 0 0 0 0

0 \* \* \* 0

0 \* \* \* 0

0 0 0 0 0

\*/

int\[\]\[\] flag = new int\[h+2\]\[w+2\];

char\[\]\[\] in = new char\[h+2\]\[w+2\];

int x = 0, y = 0, num = 1;

for (int i = 1; i <= h; i++) \{

char\[\] tmp = reader.readLine().toCharArray();

for (int j = 1; j <= w; j++) \{

in\[i\]\[j\] = tmp\[j-1\];

if (tmp\[j-1\] == '@')\{

x = i;y = j;

\}

\}

\}

int\[\] xi = \{0,0,-1,1\}, yi = \{1,-1,0,0\};

Deque queue = new ArrayDeque<>(h\*w\*2);

flag\[x\]\[y\] = 1;

queue.addLast(new Pair(x,y));

while(!queue.isEmpty())\{

Pair p = queue.pollFirst();

for (int i = 0; i < 4; i++) \{

//如果当前位置还没有走过，或者当前位置可以走(越界部分未初始化，也属于不能走的位置)

if ((flag\[p.x+xi\[i\]\]\[p.y+yi\[i\]\] != 1) && (in\[p.x+xi\[i\]\]\[p.y+yi\[i\]\] == '.'))\{

queue.addLast(new Pair(p.x+xi\[i\],p.y+yi\[i\]));

num++;

\}

//不管当前位置能不能走，都将其标记为已走过

flag\[p.x+xi\[i\]\]\[p.y+yi\[i\]\] = 1;

\}

\}

result.add(num);

temp = reader.readLine().split(" ");

if (temp\[0\].equals("0"))\{

break;

\}

\}

for (int i = 0; i < result.size(); i++) \{

writer.write(result.get(i) +"\\n");

\}

writer.flush();

\}

\}

发表评论取消回复

表情：

评论列表（有 0 条评论，11人围观）

还没有评论，来说两句吧...

相关阅读

相关 DFS之连通性模型 AcWing 1113. 红与黑

DFS之连通性模型 AcWing 1113. 红与黑原题链接 [AcWing 1113. 红与黑][AcWing 1113.] 算法标签 DFS Floo

向右看齐/ 2024年04月07日 10:19/ 0 赞/ 98 阅读

相关 java 红黑树代码

java 红黑树是一种二叉搜索树，其中的每个节点都具有颜色属性，要么是红色，要么是黑色。红黑树的节点颜色可以是"红色"或"黑色"。这种树遵循以下几条规则： 1. 每个节点要

￡神魔★判官ぃ/ 2024年03月25日 18:52/ 0 赞/ 85 阅读

相关 java算法- 红黑树

treeMap 也是使用红黑树实现的 package com.numberone.tree; / 红黑树 / pub

柔情只为你懂/ 2023年06月28日 04:51/ 0 赞/ 20 阅读

相关 java红与黑算法,AcWing 1113. 红与黑——Java宽搜版代码

import java.io.\; import java.util.\; public class Main \{ public static void main(St

布满荆棘的人生/ 2023年01月13日 10:11/ 0 赞/ 12 阅读

相关 AcWing 1113. 红与黑（BFS、DFS）

上一篇博客：[LeetCode 4. 寻找两个正序数组的中位数][LeetCode 4.] > 写在前面：大家好！我是`AC-fun`,我的昵称来自两个单词`Accepte

末蓝、/ 2023年01月06日 14:54/ 0 赞/ 175 阅读

相关红黑树java代码记录

2020-10-08目前代码只记录了插入过程和插入之后的恢复过程代码，删除过程代码还在整理. package com.lsx.tree; publi

不念不忘少年蓝@/ 2022年12月13日 01:21/ 0 赞/ 88 阅读

相关红与黑

1103: 红与黑时间限制: 1 Sec 内存限制: 32 MB 提交: 92 解决: 69 [提交][Link 1] [状态][Link 2] 题目描述

迷南。/ 2022年08月05日 05:04/ 0 赞/ 226 阅读

相关 Java数据结构与算法：红黑树

概要概述：R-B Tree，又称为“红黑树”。本文参考了《算法导论》中红黑树相关知识，加之自己的理解，然后以图文的形式对红黑树进行说明。本文的主要内容包括：红黑树的特性

我就是我/ 2022年07月13日 09:26/ 0 赞/ 236 阅读

相关 2806 红与黑

题目描述 Description 有一个矩形房间，覆盖正方形瓷砖。每块瓷砖涂成了红色或黑色。一名男子站在黑色的瓷砖上，由此出发，可以移到四个相邻瓷砖之一，但他不能移动到红砖上

╰+哭是因爲堅強的太久メ/ 2022年06月18日 08:47/ 0 赞/ 207 阅读

相关 AcWing 1113. 红与黑【 DFS深度优先搜索】题解

目录 1.题目 2思路 3.代码 1.题目有一间长方形的房子，地上铺了红色、黑色两

比眉伴天荒/ 2021年07月24日 21:30/ 0 赞/ 329 阅读