算法-渗透问题
问题描述:
渗透问题,给一个n*m的矩阵,0为空白,1为白纸,2为墨水,墨水每经过每一秒会将上下左右相邻的白纸染成黑色,然后继续渗透,判断此图中的白纸最终是否能够全部被墨水染上色,若能需要输出所有白纸全部被墨水染上色的时间。
java代码实现:
package com.example.demo.controller;
import java.util.ArrayList;
import java.util.List;
public class Test5Controller {
//上下左右四个方向的增量
static int move[][]=new int[][] {{0,0},{0,1},{1,0},{0,-1},{-1,0}};
static int t[][]=new int[][] {
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,1,0,0,0,0,0,0,0},
{0,1,2,1,1,1,0,0,0,0},
{0,0,1,0,0,0,0,0,0,0},
{0,0,1,0,0,0,0,0,0,0},
{0,1,1,1,1,1,1,1,1,2},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0}};
public static void main(String[] args) {
List<Node> li=new ArrayList<>();
//先将开始时所有的墨水放入集合
for(int i=0;i<t.length;i++) {
for(int j=0;j<t[i].length;j++) {
if(t[i][j]==2) {
li.add(new Node(i,j,2));
}
}
}
//总时间c
int c=0;
do {
li=search(li);
if(li.size()>0) {
//如果集合里面有数据,那就向外扩散一次
c++;
}else {
break;
}
}while(true);
/**
* 看是否所有的纸都被染色
*/
for(int i=0;i<t.length;i++) {
for(int j=0;j<t[i].length;j++) {
if(t[i][j]==1) {
System.out.println("false");
return;
}
}
}
System.out.println("time:"+c);
}
public static List<Node> search(List<Node> list){
List<Node> li=new ArrayList<>();
/**
* 遍历每个周围节点
*/
for(Node n:list) {
/**
* 遍历每个节点的四个方向
*/
for(int i=1;i<=4;i++) {
int x=n.x+move[i][0];
int y=n.y+move[i][1];
//控制边界
if(x<t.length&&y<t[0].length&&t[x][y]==1) {
t[x][y]=2;
li.add(new Node(x,y,t[x][y]));
}
}
}
return li;
}
/**
* 模拟节点类
*/
static class Node{
public int x;//数组横坐标
public int y;//数组纵坐标
public int d;//数据
public Node(int x, int y, int d) {
super();
this.x = x;
this.y = y;
this.d = d;
}
@Override
public String toString() {
return "Node [x=" + x + ", y=" + y + ", d=" + d + "]";
}
}
}
评论区
请写下您的评论...
猜你喜欢
blog
算法-求和问题
数据结构与算法
12321
(returnnewint[]={1,2}),如果没有返回-1(returnnewint[]={-1,-1})。算法:用查找表解决问题实现:packageclub.test;importjava.util.HashMap;im
blog
枚举算法案例--熄灯问题
数据结构与算法
6480
熄灯问题1.问题描述有一个有按钮组成的矩阵,其中每行有6个按钮,共5行。每个按钮的位置上有一盏灯。当按下一个按钮后,该按钮以及周围位置(上下左右)的灯都会改变一次。即(原来亮的变暗,原来暗的变亮)对
blog
算法-迷宫问题-广度优先搜索-队列
数据结构与算法
9004
问题描述思路:典型的广度优先搜索算法,根据字典序大小,可以确定遍历的循序,因为字典序DLRU,所以对于每一个节点优先先往下走,然后向左走,然后向右走,然后向上走。则最后首先到达出口的一条路径就是符合
weblog
10126
什么是floyd算法在计算机科学中,Floyd-Warshall算法是一种在具有正或负边缘权重(但没有负周期)的加权图中找到最短路径的算法。算法的单个执行将找到所有顶点对之间的最短路径的长度(加权
blog
八皇后问题
数据结构与算法
7256
八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行
数据结构与算法
1629
约瑟夫环问题描述有m个人,围成一个环,编号为1、2、3、、、m,从第一个人开始循环报数(从1开始数),假设数到n的那个人出局,然后从下一个人继续数数(从1开始数),数到n出列,以此循环,最后那个人为
ofc
c#方法参数传值问题
weblog
3818
值类型的传值参数方法执行时会为实参创建一个副本,方法内改变形参的值时不会改变实参的值。引用类型的传值参数方法会为实参创建一个副本引用,形参和实参指向的是同一个对象的内存地址,当形参引用的内存地址改变
blog
温故01背包问题
数据结构与算法
5977
01背包问题是动态规划算法的一个经典例题:题目: 在n种物品中选取若干件(每种物品只有一件只能选择一次) 放在空间为W的背包里,每种物品的体积为wigth[1],wigth[2],wigth[3
最新发表
归档
2018-11
12
2018-12
33
2019-01
28
2019-02
28
2019-03
32
2019-04
27
2019-05
33
2019-06
6
2019-07
12
2019-08
12
2019-09
21
2019-10
8
2019-11
15
2019-12
25
2020-01
9
2020-02
5
2020-03
16
2020-04
4
2020-06
1
2020-07
7
2020-08
13
2020-09
9
2020-10
5
2020-12
3
2021-01
1
2021-02
5
2021-03
7
2021-04
4
2021-05
4
2021-06
1
2021-07
7
2021-08
2
2021-09
8
2021-10
9
2021-11
16
2021-12
14
2022-01
7
2022-05
1
2022-08
3
2022-09
2
2022-10
2
2022-12
5
2023-01
3
2023-02
1
2023-03
4
2023-04
2
2023-06
3
2023-07
4
2023-08
1
2023-10
1
2024-02
1
2024-03
1
2024-04
1
标签
算法基础
linux
前端
c++
数据结构
框架
数据库
计算机基础
储备知识
java基础
ASM
其他
深入理解java虚拟机
nginx
git
消息中间件
搜索
maven
redis
docker
dubbo
vue
导入导出
软件使用
idea插件
协议
无聊的知识
jenkins
springboot
mqtt协议
keepalived
minio
mysql
ensp
网络基础
xxl-job
rabbitmq
haproxy
srs
音视频
webrtc
javascript
目录
没有一个冬天不可逾越,没有一个春天不会来临。最慢的步伐不是跬步,而是徘徊,最快的脚步不是冲刺,而是坚持。