1815:画家问题 (dfs java)

2023-10-12 07:50
文章标签 java 问题 dfs 画家 1815

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

题目链接
在这里插入图片描述
在这里插入图片描述
和熄灯问题很像。如果暴力搜索的话,棋盘大小15*15,每个位置的状态有两个变或者不变,那么将有 2 15 ∗ 15 2^{15*15} 21515个状态,显然不能直接搜。事实上,我们可以枚举第一行的状态,因为第一行的状态一旦确定,剩余行也随之确定,这是因为对于与第一行的w,只能是第二行的这个位置修改才能使得第一行的‘w’变为’y’,其他行的修改不会影响到第一行,同理,第二行确定后,只能由第三行改变第二行为‘w’的位置。最后只需要检查最后一行是否都为‘y’即可。
所以枚举第一行的状态就只有 2 16 2^{16} 216个状态了。
需要注意的是,要及时恢复棋盘原来的状态,这一点在枚举第一行状态的时候很容易想到,但是当枚举完第一行状态进行check是否是可行的方案时,需要重新建立一个棋盘的副本去检查,因为检查的过程也涉及到颜色的改变,检查完毕之后接着dfs应该用的是原来的棋盘。

import java.util.*;public class Main{public static char[][] G=new char[16][16];public static int[] dx= {0,0,-1,1};public static int[] dy= {-1,1,0,0};public static int ans=0x3f3f3f3f;public static Map<Character,Character> mp=new HashMap<Character,Character>();public static void change(int x,int y,int n,char[][] g) {//改变(x,y)及上下左右的颜色//change两次就相当于没有changeg[x][y]=mp.get(g[x][y]);for(int i=0;i<4;i++) {int newx=x+dx[i];int newy=y+dy[i];if(newx<0 || newx>=n || newy<0 || newy>=n) {continue;}g[newx][newy]=mp.get(g[newx][newy]);}}public static int check(char[][]tmpG,int n) {//根据第一行的状态改变剩余行的状态int cnt=0;for(int i=1;i<n;i++) {for(int j=0;j<n;j++) {if(tmpG[i-1][j]=='w') {cnt++;change(i,j,n,tmpG);}}}for(int j=0;j<n;j++) {if(tmpG[n-1][j]=='w') {return 0x3f3f3f3f;}}return cnt;}public static void dfs(int pos,int n,int CNT) {//当前位置pos有两种状态,改/不改if(pos==n) {//第一行的状态枚举完毕,检查是否都变为黄色char[][] tmpG=new char[16][16];for(int i=0;i<n;i++) {for(int j=0;j<n;j++) {tmpG[i][j]=G[i][j];}}ans=Math.min(check(tmpG,n)+CNT,ans);return;//递归终止之后记得返回,否则还会执行后面}change(0,pos,n,G);//改dfs(pos+1,n,CNT+1);change(0,pos,n,G);//撤销改,即不改dfs(pos+1,n,CNT);}public static void main(String[] Args) {mp.put('w', 'y');mp.put('y', 'w');Scanner sc=new Scanner(System.in);int n;n=sc.nextInt();sc.nextLine();//吸收enterfor(int i=0;i<n;i++) {String tmp;tmp=sc.nextLine();for(int j=0;j<n;j++) {G[i][j]=tmp.charAt(j);}}//枚举第一行的状态,每个位置可以变或者不变//第一行状态选定后,其他行的状态就随之确定了dfs(0,n,0);if(ans==0x3f3f3f3f) {System.out.print("inf");}else {System.out.print(ans);}
//		for(int i=0;i<n;i++) {
//			for(int j=0;j<n;j++) {
//				System.out.print(G[i][j]+" ");
//			}
//			System.out.println();
//		}}
}

这篇关于1815:画家问题 (dfs java)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Java实现MD5加密的四种方式

《Java实现MD5加密的四种方式》MD5是一种广泛使用的哈希算法,其输出结果是一个128位的二进制数,通常以32位十六进制数的形式表示,MD5的底层实现涉及多个复杂的步骤和算法,本文给大家介绍了Ja... 目录MD5介绍Java 中实现 MD5 加密方式方法一:使用 MessageDigest方法二:使用

Java中的runnable 和 callable 区别解析

《Java中的runnable和callable区别解析》Runnable接口用于定义不需要返回结果的任务,而Callable接口可以返回结果并抛出异常,通常与Future结合使用,Runnab... 目录1. Runnable接口1.1 Runnable的定义1.2 Runnable的特点1.3 使用Ru

Java中Runnable和Callable的区别和联系及使用场景

《Java中Runnable和Callable的区别和联系及使用场景》Java多线程有两个重要的接口,Runnable和Callable,分别提供一个run方法和call方法,二者是有较大差异的,本文... 目录一、Runnable使用场景二、Callable的使用场景三、关于Future和FutureTa

Spring 中 BeanFactoryPostProcessor 的作用和示例源码分析

《Spring中BeanFactoryPostProcessor的作用和示例源码分析》Spring的BeanFactoryPostProcessor是容器初始化的扩展接口,允许在Bean实例化前... 目录一、概览1. 核心定位2. 核心功能详解3. 关键特性二、Spring 内置的 BeanFactory

Spring组件初始化扩展点BeanPostProcessor的作用详解

《Spring组件初始化扩展点BeanPostProcessor的作用详解》本文通过实战案例和常见应用场景详细介绍了BeanPostProcessor的使用,并强调了其在Spring扩展中的重要性,感... 目录一、概述二、BeanPostProcessor的作用三、核心方法解析1、postProcessB

Java导入、导出excel用法步骤保姆级教程(附封装好的工具类)

《Java导入、导出excel用法步骤保姆级教程(附封装好的工具类)》:本文主要介绍Java导入、导出excel的相关资料,讲解了使用Java和ApachePOI库将数据导出为Excel文件,包括... 目录前言一、引入Apache POI依赖二、用法&步骤2.1 创建Excel的元素2.3 样式和字体2.

Java实现将Markdown转换为纯文本

《Java实现将Markdown转换为纯文本》这篇文章主要为大家详细介绍了两种在Java中实现Markdown转纯文本的主流方法,文中的示例代码讲解详细,大家可以根据需求选择适合的方案... 目录方法一:使用正则表达式(轻量级方案)方法二:使用 Flexmark-Java 库(专业方案)1. 添加依赖(Ma

Spring Boot拦截器Interceptor与过滤器Filter详细教程(示例详解)

《SpringBoot拦截器Interceptor与过滤器Filter详细教程(示例详解)》本文详细介绍了SpringBoot中的拦截器(Interceptor)和过滤器(Filter),包括它们的... 目录Spring Boot拦截器(Interceptor)与过滤器(Filter)详细教程1. 概述1

SpringBoot利用dynamic-datasource-spring-boot-starter解决多数据源问题

《SpringBoot利用dynamic-datasource-spring-boot-starter解决多数据源问题》dynamic-datasource-spring-boot-starter是一... 目录概要整体架构构想操作步骤创建数据源切换数据源后续问题小结概要自己闲暇时间想实现一个多租户平台,

VSCode中C/C++编码乱码问题的两种解决方法

《VSCode中C/C++编码乱码问题的两种解决方法》在中国地区,Windows系统中的cmd和PowerShell默认编码是GBK,但VSCode默认使用UTF-8编码,这种编码不一致会导致在VSC... 目录问题方法一:通过 Code Runner 插件调整编码配置步骤方法二:在 PowerShell