PTA 2813:画家问题(熄灯问题)

有一个正方形的墙,由NN个正方形的砖组成,其中一些砖是白色的,另外一些砖是黄色的。Bob是个画家,想把全部的砖都涂成黄色。但他的画笔不好使。当他用画笔涂画第(i,j)个位置的砖时, 位置(i−1,j)、 (i+1,j)、(i,j−1)、(i,j+1)上的砖都会改变颜色。请你帮助Bob计算出最少需要涂画多少块砖,才能使所有砖的颜色都变成黄色。

1-1.jpg

输入格式:

第一行是一个整数n (1≤n ≤16),表示墙的大小。接下来的n行表示墙的初始状态。每一行包含n个字符。第i行的第j个字符表示位于位置(i,j)上的砖的颜色。“w”表示白砖,“y”表示黄砖。

输出格式:

一行,如果Bob能够将所有的砖都涂成黄色,则输出最少需要涂画的砖数,否则输出“inf”。

输入样例:

在这里给出一组输入。例如:

5
wwwww
wwwww
wwwww
wwwww
wwwww

输出样例:

在这里给出相应的输出。例如:

15

熄灯问题没什么好方法,只能一层一层推导。

AC代码:

#indpude<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl "\n"

const ll N = 1e1+7 ,M = 1e5+7;
ll n;
ll color[N][N],dp[N][N];

ll pd(ll z){
	for(ll i = 1 ; i < z ; i ++)//尝试涂色,当前点的颜色由初始画板和涂色区推出 
		for(ll j = 1 ; j <= z ; j ++)
			dp[i+1][j]=(color[i][j]+dp[i-1][j]+dp[i][j-1]+dp[i][j]+dp[i][j+1])%2;
	for(ll i = 1 ; i <= z ; i ++)//由最后一行判断当前涂色能否成功 
		if(color[z][i] != (dp[z-1][i]+dp[z][i-1]+dp[z][i]+dp[z][i+1])%2)return M;
	ll sum=0;//算涂色次数 
	for(ll i = 1 ; i <= z ; i ++)
		for(ll j = 1 ; j <= z ; j ++)
			if(dp[i][j])sum++;
	return sum;
}

ll found(ll x){
	ll sum = M ,cnt = 0 ,y;
	while(dp[1][x+1] < 1){
		cnt = pd(x);
		if(cnt < sum)sum=cnt;
		dp[1][1]++;
		y=1;
		while(dp[1][y] > 1){
			dp[1][y]=0;
			y++;
			dp[1][y]++;
		}
	}
	return sum;
}

void solve(){
	memset(dp,0,sizeof dp);
	memset(color,0,sizeof color);
	cin >> n;
	for(ll i = 1 ; i <= n ; i ++)
		for(ll j = 1 ; j <= n ; j ++){
			char c;cin >> c;
			if(c == 'w')color[i][j]=1;
		}
	ll sum = found(n);
	sum == M ? cout << "inf" << endl : cout << sum << endl;
	return;
}

int main(){
	ll t=1;//cin >> t;
	while(t --)solve();
	return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/533091.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

HJ13 句子逆序(句子反序,再把单词反序)

句子反序&#xff0c;再把单词反序 import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别String s sc.n…

本地化部署离线开源免费语音识别API,支持多模态AI能力引擎

思通数科作为一家专注于多模态AI能力开源引擎平台&#xff0c;其技术产品涵盖了自然语言处理、情感分析、实体识别、图像识别与分类、OCR识别以及语音识别等多个领域。在语音识别这一细分市场&#xff0c;思通数科的技术产品中的音频文件转写服务有着相似的应用场景和功能特点。…

如何将powerpoint(PPT)幻灯片嵌入网页中在线预览、编辑并保存到服务器?

猿大师办公助手不仅可以把微软Office、金山WPS和永中Office的Word文档、Excel表格内嵌到浏览器网页中实现在线预览、编辑保存等操作&#xff0c;还可以把微软Office、金山WPS和永中Office的PPT幻灯片实现网页中在线预览、编辑并保存到服务器。 猿大师办公助手把本机原生Office…

【开发篇】十三、JVM基础参数设置与垃圾回收器的选择

文章目录 1、-Xmx 和 –Xms2、-XX:MaxMetaspaceSize 和 –XX:MetaspaceSize3、-Xss4、不建议改的参数5、其他参数6、选择GC回收器的调试思路7、CMS的并发模式失败现象的解决8、调优案例 GC问题解决方式&#xff1a; 优化JVM基础参数&#xff0c;避免频繁Full GC减少对象的产生…

设计模式学习笔记 - 设计模式与范式 -行为型:9.迭代器模式(上):相比直接遍历集合数据,使用迭代器模式有哪些优势?

概述 上篇文章&#xff0c;我们学习了状态模式。状态模式是状态机的一种实现方式。它通过将事件触发的状态转移和动作执行&#xff0c;拆分到不同的状态类中&#xff0c;以此来避免状态机类中的分支判断逻辑&#xff0c;应对状态机类代码的复杂性。 本章&#xff0c;学习另外…

Day20_学点儿JavaEE_基于Session的登录、数据库null值正确显示

1 登录 使用Session技术完成用户登录的功能&#xff1a; 登录功能会使用到Session&#xff0c;把用户登录的用户名和密码保存到Session&#xff0c;因为Session是属于每个用户独有的&#xff0c;就可以记录每个用户单独的登录信息。 当然&#xff0c;这仅仅是完成了一个简单的…

windows安装charles抓包iphone

安装charles抓包iphone charles基础介绍windows安装 charles基础介绍 Charles 是在 PC 端常用的网络封包截取工具&#xff0c;在做移动开发时&#xff0c;我们为了调试与服务器端的网络通讯协议&#xff0c;常常需要截取网络封包来分析。除了在做移动开发中调试端口外&#xf…

探索GlusterFS:开源分布式文件系统

目录 引言 一、GlusterFS简介 &#xff08;一&#xff09;基本介绍 &#xff08;二&#xff09;GlusterFS特点 &#xff08;三&#xff09;GlusterFS术语 &#xff08;四&#xff09;GlusterFS工作流程 二、GlusterFs的卷类型 &#xff08;一&#xff09;卷类型 &…

vue3中使用antv-S2表格(基础功能版)

先看展示效果&#xff1a; 可以调整行宽、列宽、自定义字段图标、表头图标、添加排序、显示总计、小计等 首先确保搭建一个vue3项目环境&#xff0c;从0开始的小伙伴着重看第一点&#xff1a; 一、搭建vue3项目环境 首先创建一个vue3vitets项目&#xff0c;可以查看下面相关…

铸造大型基础平板的结构应该怎样设计

设计大型基础平板的结构时&#xff0c;需要考虑以下几个方面&#xff1a; 地质条件&#xff1a;首先要了解工程所在地的地质条件&#xff0c;包括土质、地下水位、地震状况等。根据地质条件来选择合适的基础类型&#xff0c;如浅基、深基或地下连续墙等。 荷载分析&#xff1a…

Lumos学习python第九课:VSCode+Anaconda

注意Anaconda版本和Python版本的对应关系&#xff0c;同一个Anaconda可以支持多个Python版本&#xff0c; 注&#xff1a;现在vscode已原生支持jupyter notebook&#xff08;要求Python版本>3.6&#xff09; Anaconda在Python解析器的基础上封装了很多Python包&#xff0c…

Weblogic任意文件上传漏洞(CVE-2018-2894)漏洞复现(基于vulhub)

&#x1f36c; 博主介绍&#x1f468;‍&#x1f393; 博主介绍&#xff1a;大家好&#xff0c;我是 hacker-routing &#xff0c;很高兴认识大家~ ✨主攻领域&#xff1a;【渗透领域】【应急响应】 【Java、PHP】 【VulnHub靶场复现】【面试分析】 &#x1f389;点赞➕评论➕收…

C++模板编程

模板是泛型编程的基础&#xff0c;先给出泛型编程的概念。 泛型编程&#xff1a;编写与类型无关的通用代码&#xff0c;是代码复用的一种手段。 应用场景&#xff1a;比如要实现一个通用的&#xff0c;进行两个变量互相交换的函数&#xff0c;此时可以通过函数重载的方式&…

Ubuntu配置VScode的C++环境

在Ubuntu系统下配置C环境&#xff0c;并运行helloworld 1. 下载VScode 我这里使用的是星火应用商店&#xff0c;在商店里面可以直接下载安装 http://spark-app.store/ 2.创建文件夹 3.启动VScode并打开该文件夹 4.安装以下几个扩展 PS&#xff1a;Clang这个插件别安装&…

3. DAX 时间函数-- DATE 日期--一生二,二生三,三生万物

在数据分析过程中&#xff0c;经常需要从一个数据推到另外一个数据&#xff0c;日期数据也是如此&#xff0c;需要从一个日期推到另外一个相关的日期&#xff0c;或者从一群日期推到另外一个相关的日期/一群相关的日期。这一期说的就是日期之间彼此推衍的函数&#xff0c;会比之…

C# 操作PDF表单 - 创建、填写、删除PDF表单域

通常情况下&#xff0c;PDF文件是不可编辑的&#xff0c;但PDF表单提供了一些可编辑区域&#xff0c;允许用户填写和提交信息。PDF表单通常用于收集信息、反馈或进行在线申请&#xff0c;是许多行业中数据收集和交换的重要工具。 PDF表单可以包含各种类型的输入控件&#xff0…

QT:事件机制

作业&#xff1a; widget.h #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QTimerEvent> #include <QTime> #include<QPushButton> #include <QTextToSpeech>QT_BEGIN_NAMESPACE namespace Ui { class Widget; } QT_END_NAME…

头歌-机器学习 第15次实验 朴素贝叶斯分类器

第1关:条件概率 任务描述 本关任务:根据本节课所学知识完成本关所设置的选择题。 相关知识 为了完成本关任务,你需要掌握条件概率。 条件概率 朴素贝叶斯分类算法是基于贝叶斯定理与特征条件独立假设的分类方法,因此想要了解朴素贝叶斯分类算法背后的算法原理,就不得…

【CSS】一篇文章讲清楚screen、window和html元素的位置:top、left、width、height

一个Web网页从内到外的顺序是&#xff1a; 元素div,ul,table... → 页面body → 浏览器window → 屏幕screen 分类详情屏幕screen srceen.width - 屏幕的宽度 screen.height - 屏幕的高度&#xff08;屏幕未缩放时&#xff0c;表示屏幕分辨率&#xff09; screen.availLeft …

(一)基于IDEA的JAVA基础13

数组遍历 遍历数组就是把数组内的数据一个个的取出来 1.我们可以用for循环&#xff0c;依次把数字类的元素取出来。 2.增强型for循环。 用第一个方法写一下&#xff0c;看一下 public class Test01 { public static void main(String[] args) { //存储一组数据{…