程序地带

寒假打卡day4——1113. 红与黑


在这里插入图片描述


acwing 1113. 红与黑


Flood Fill 洪水灌溉算法


BFS

模板:


while 队列非空{
取出队头;
枚举队头的四个邻格{
if 各格子是陆地且为被开发过
标记为开发过
插入队列
}
}
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
/**
* @author JohnnyLin
* @version Creation Time:2021年1月14日 下午10:01:17
*
*/
class Node{
int x, y;
public Node(int x, int y) {//注意赋值是最好用this.
this.x = x;
this.y = y;
}
}
public class Main {
//顺时针方向
static int dir[][] = {{-1,0},{0,1},{1,0},{0,-1}};
static int N = 25;
static int m;
static int n;
static char[][] map = new char[N][N];
public static int bfs(int sx,int sy) {
int cnt = 1;
Queue<Node> q = new LinkedList<Node>();
//标记为已经访问过
q.add(new Node(sx, sy));
//标记为红砖
map[sx][sy] = '#';
while(!q.isEmpty()) {
//取出队头
Node node = q.peek();
q.poll();
//枚举队头的四个邻格
for(int i = 0; i < 4; i++) {
int nx = node.x + dir[i][0];
int ny = node.y + dir[i][1];
//越界或者访问过或者不为黑砖
if(nx < 0 || nx >= m || ny < 0 || ny >=n || map[nx][ny]!='.')
continue;
//应该在此处标记访问过
map[nx][ny] = '#';
q.offer(new Node(nx,ny));
cnt ++;
}
}
return cnt;
}
public static void main(String[] args) {
Scanner reader = new Scanner(System.in);
while(true) {
n = reader.nextInt();//列
m = reader.nextInt();//行
if( m ==0|| n == 0)
break;
int sx = 0, sy = 0;
for(int i = 0; i < m; i++) {
String s = reader.next();
for(int j = 0; j < n; j++) {
map [i][j] = s.charAt(j);
if(map [i][j] == '@') {
sx = i;
sy = j;
}
}
}
System.out.println(bfs(sx, sy) );
}
}
}
DFS

模板


dfs(x,y){
将(x,y)标记为开发;
枚举(x,y)的4个邻格;
if 邻格可走
dfs(邻格);
}
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
/**
* @author JohnnyLin
* @version Creation Time:2021年1月14日 下午10:01:17
*
*/
public class Main {
//顺时针方向
static int dir[][] = {{-1,0},{0,1},{1,0},{0,-1}};
static int N = 25;
static int m;
static int n;
static char[][] map = new char[N][N];
static boolean[][] vis = new boolean[N][N];//记录该点是否遍历过
public static int dfs(int sx,int sy) {
int res = 1;
map[sx][sy] = '#';
//枚举(sx,sy)的四个邻格
for(int i = 0; i < 4; i++) {
//如果邻格可走
int nx = sx + dir[i][0], ny = sy +dir[i][1];
if(nx >= 0 && nx < m && ny >= 0 && ny < n && map[nx][ny] =='.') {
res += dfs(nx, ny);
}
}
return res;
}
public static void main(String[] args) {
Scanner reader = new Scanner(System.in);
while(true) {
n = reader.nextInt();//列
m = reader.nextInt();//行
if( m ==0|| n == 0)
break;
int sx = 0, sy = 0;
for(int i = 0; i < m; i++) {
String s = reader.next();
for(int j = 0; j < n; j++) {
map [i][j] = s.charAt(j);
if(map [i][j] == '@') {
sx = i;
sy = j;
}
}
}
System.out.println(dfs(sx, sy) );
}
}
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_44855907/article/details/112689239

随机推荐

WPF中调用winform

1.添加引用:WindowsFormsIntegration.dll(负责整合WPF和Windows)、System.Windows.Forms.2.在XAM...

昨晚早睡了没 阅读(701)

Dynamics 365 报表使用日志记录查询及相关扩展

Dynamics365报表使用日志记录查询及相关扩展获取用户查询报表的历史记录备份表“曲线救国”获取用户查询报表的历史记录selectSUBSTRING(cl.Description,1,LEN(cl...

mu_sang 阅读(296)

pygame的一些基础语法

文章目录1.实现图像的由小变大2.Rect的碰撞1.实现图像的由小变大inflate_ip()以矩形区域的中心点为中心,像四周扩大或者缩小。inflte_ip(x,y)x表示水平方向缩放...

奔前程的水手 阅读(872)

MySQL数据库部署解析

文章目录一、数据库1、数据库的基本概念1.1数据(Data)1.2表1.3数据库1.4数据库管理系统(DBMS)1.5数据库系统2、数据库系统发...

林魏国 阅读(709)

Django——三种路径

1.django中的三种路径1.1操作系统文件绝对路径django静态文件查找,模板查找(第一种)#去配置好的文件夹中查找指定的文件BASE_DIR=os.path...

故玖.9 阅读(950)

CentOS 8 安装 docker/docker-compose

安装依赖sudodnf-yinstallyum-utils device-mapper-persistent-data lvm2sudoyum-config-manager--add-repo htt...

happyzwh 阅读(120)

mysql 表空间收缩_MySQL表空间回收的正确姿势

不知道大家有没有遇到这样的一种情况,线上业务在MySQL表上做增删改查操作,随着时间的推移,表里面的数据越来越多,表数据文件越来越大࿰...

冰淇淋红茶全糖 阅读(936)