Codeforces Round 928 F. Vlad and Avoiding X

news/2025/2/12 15:29:42/

原题链接:Problem - F - Codeforces

题目大意:多组询问,给一个7×7的棋盘,上面有W和B二种棋子,棋盘不允许B棋子的左上角,左下角,右上角,右下角也是B,可以让W变成B,也可以让B变成W,问最少的变化次数。

思路:棋盘的纵向为i,横向为j,当(i+j)%2==0,当前点涂为白色,当(i+j)%2==1,当前的点涂为黑色。可以将白色棋盘和黑色棋盘分开观察。对应白色棋盘来说,观察可以知道,如果白色棋盘出现了非法的结构,那么最多变化4次就可以让白色棋盘满足条件,黑色棋盘也是如此。那么就可以设置二个最小值,一个记录白色棋盘,一个记录黑色棋盘。使用dfs分别遍历白色棋盘和黑色棋盘,然后最小值相加就是答案。

特别的:如果遍历白色棋盘,出现非法结构,那么非法结构的棋子一定都在白色棋盘上,黑色棋盘也是。

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define endl '\n' 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,char> pii;
const int N=1e6+10,mod=1e9+7;
char mp[10][10];
ll min1=1e18,min2=1e18;
void dfs1(ll x,ll y,ll sum)
{if(sum>min1||sum>5)return;//超过4次改变一定不是最优的改变 if((x+y)%2==1)//只遍历黑色棋盘 {dfs1(x,y+1,sum);return;}if(y>=7){dfs1(x+1,0,sum);return;}if(x>=7){min1=min(min1,sum);return;}if(mp[x][y]=='B'&&mp[x][y+2]=='B'&&mp[x+1][y+1]=='B'&&mp[x+2][y+2]=='B'&&mp[x+2][y]=='B')//一个非法结构共五个B,分别变化他们,求最小值 {mp[x][y]='W';dfs1(x,y+1,sum+1);mp[x][y]='B';mp[x][y+2]='W';dfs1(x,y+1,sum+1);mp[x][y+2]='B';mp[x+1][y+1]='W';dfs1(x,y+1,sum+1);mp[x+1][y+1]='B';mp[x+2][y+2]='W';dfs1(x,y+1,sum+1);mp[x+2][y+2]='B';mp[x+2][y]='W';dfs1(x,y+1,sum+1);mp[x+2][y]='B';}else dfs1(x,y+1,sum);
}
void dfs2(ll x,ll y,ll sum)
{if(sum>min2||sum>5)return;if((x+y)%2==0){dfs2(x,y+1,sum);return;}if(y>=7){dfs2(x+1,0,sum);return;}if(x>=7){min2=min(min2,sum);return;}if(mp[x][y]=='B'&&mp[x][y+2]=='B'&&mp[x+1][y+1]=='B'&&mp[x+2][y+2]=='B'&&mp[x+2][y]=='B'){mp[x][y]='W';dfs2(x,y+1,sum+1);mp[x][y]='B';mp[x][y+2]='W';dfs2(x,y+1,sum+1);mp[x][y+2]='B';mp[x+1][y+1]='W';dfs2(x,y+1,sum+1);mp[x+1][y+1]='B';mp[x+2][y+2]='W';dfs2(x,y+1,sum+1);mp[x+2][y+2]='B';mp[x+2][y]='W';dfs2(x,y+1,sum+1);mp[x+2][y]='B';}else dfs2(x,y+1,sum);
}
int main()
{ios::sync_with_stdio(NULL);cin.tie(0),cout.tie(0);ll t;cin>>t;while(t--){for(int i=0;i<7;i++){for(int j=0;j<7;j++)cin>>mp[i][j];}min1=min2=1e18;dfs1(0,0,0);dfs2(0,1,0);cout<<min1+min2<<endl;}return 0;
}


http://www.ppmy.cn/news/1361028.html

相关文章

Spring RabbitMQ 配置多个虚拟主机(vhost)

文章目录 前言一、相关文章二、相关代码1.yml文件配置2.RabbitMq配置类3.接收MQ消息前言 在日常开发中,同时需要用到RabbitMQ多个虚拟机(vhost)。应用场景:需要接收多个交换机的数据,而交换机都在不同的虚拟机(vhost) 一、相关文章 Docker安装RabbitMQ 【SpringCloud…

vue里echarts的使用:画饼图和面积折线图

vue里echarts的使用,我们要先安装echarts,然后在main.js里引入: //命令安装echarts npm i echarts//main.js里引入挂载到原型上 import echarts from echarts Vue.prototype.$echarts = echarts最终我们实现的效果如下: 头部标题这里我们封装了一个全局公共组件common-he…

常用的制造企业网络优化方案

在制造业企业不断加速转型的情况下&#xff0c;企业内部数据传输面临了更高的要求。在企业的多站点内部网络互联互通方面&#xff0c;常见的组网网络优化方案有多种选择&#xff0c;每种都有其独特的优势。以下是其中VPN、MPLS、SD-WAN三种主要的组网方案&#xff1a; 1. VPN&a…

centos7下docker的安装

背景 总结下docker的一些知识 docker安装&#xff08;有网络版&#xff09; 参考文章我以前试过这个帖子&#xff0c;建议安装高版本的docker&#xff0c;&#xff08;20以上的&#xff0c;不然可能会有一些问题&#xff09; ## 1、安装依赖 [rootiZo7e61fz42ik0Z ~]#yum i…

《图解设计模式》笔记(一)适应设计模式

图灵社区 - 图解设计模式 - 随书下载 评论区 雨帆 2017-01-11 16:14:04 对于设计模式&#xff0c;我个人认为&#xff0c;其实代码和设计原则才是最好的老师。理解了 SOLID&#xff0c;如何 SOLID&#xff0c;自然而然地就用起来设计模式了。Github 上有一个 tdd-training&…

C# 实现网页内容保存为图片并生成压缩包

目录 应用场景 实现代码 扩展功能(生成压缩包) 小结 应用场景 我们在一个求职简历打印的项目功能里&#xff0c;需要根据一定的查询条件&#xff0c;得到结果并批量导出指定格式的文件。导出的格式可能有多种&#xff0c;比如WORD格式、EXCEL格式、PDF格式等&#xff0c;…

【设计模式】01-装饰器模式Decorator

作用&#xff1a;在不修改对象外观和功能的情况下添加或者删除对象功能&#xff0c;即给一个对象动态附加职能 装饰器模式主要包含以下角色。 抽象构件&#xff08;Component&#xff09;角色&#xff1a;定义一个抽象接口以规范准备接收附加责任的对象。具体构件&#xff08…

Git diff Word 文档

前言 前段时间用 nodeJS 写了一个提交代码的工具&#xff0c;开发过程中在认证部分遇到了一些小问题&#xff0c;于是就想看看官方的文档中有没有什么说明之类的&#xff0c;没想到文档中的内容十分丰富&#xff0c;除了解释了 git 相关的原理外&#xff0c;还学到了很多有用的…