当前位置:网站首页>The second session of the question swiping and punching activity -- solving the switching problem with recursion as the background (I)
The second session of the question swiping and punching activity -- solving the switching problem with recursion as the background (I)
2022-07-04 07:54:00 【Poplar branch】
AcWing 95. Inexplicable switch day03 【C++】
Title Description
source :acwing
Original title transmission gate
Problem solving report
One 、 Understanding of topic meaning
Players change the state of a light and have a chain reaction : And this lamp up and down adjacent to the left and right lights should also change their state accordingly .
Use windows Own drawing , Hold on shift Drag the mouse to draw the following graphics for demonstration .
Sample demonstration :
Two 、 The operation of each line of switch is completely determined by the light on and off of the previous line
- Suppose all the states in the first row are determined by enumeration , Each switch is either pressed , Or don't press , Here it is 2 5 2^5 25 Secondary selection .
- According to the light off state of the previous line , Decide how to press the next line , To ensure that the previous line is bright .
3、 ... and 、 The details are finalized
- How to enumerate the first line 32 In the operation . A five bit binary can just represent this 32 Kind of operation . such as
11010 => Corresponding to the first 26 Operations . that 0 ~ 2 5 2^5 25-1 You can enumerate the first row one by one 32 Kind of plan
Switch on function
After clicking the switch in one position , Its four position switches will be changed . Use four i f if if It seems too troublesome . What is considered here is to add Offset implementation .Time complexity
32 ∗ 25 ∗ 5 ∗ 500 = 2000000 32 * 25 * 5 * 500 = 2000000 32∗25∗5∗500=2000000, About twomillion calculations . There is no problem at all
Reference code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 6;
char g[N][N],backup[N][N];
int dx[] = {-1,0,1,0,0} , dy[] = {0,-1,0,1,0};
// completion turn function
void turn(int x,int y)
{
for(int i = 0; i < 5;i++)
{
int a = x+dx[i] , b = y + dy[i];
// Judgement boundary
if(a < 0 || a >= 5 || b < 0 || b>= 5) continue;
// Update status
g[a][b] ^= 1;
}
}
int main()
{
int T;
cin >> T;
while(T--)
{
// Building maps
for(int i = 0; i < 5;i++) cin >> g[i];
int res = 10;// Record answer
// Enumerate the first line of 32 A choice
for(int op = 0; op < 32;op++)
{
memcpy(backup,g,sizeof g);
int step = 0;// Record the steps performed
// Deal with whether there is a light that can be pressed on in the current scheme
for(int i = 0; i < 5; i++)
{
if(!(op >> i &1))
{
step ++;
turn(0,i);
}
}
// According to the current situation in the first line , Deal with the processing of the next four lines
for(int i = 0; i < 4;i++)
{
for(int j = 0; j < 5;j++)
if(g[i][j] == '0')
{
step ++;
turn(i+1,j);
}
}
// Traverse the last line , If there is a black lamp , Then the current scheme fails
bool dark = false;// Mark
for(int i = 0; i < 5;i++)
if(g[4][i] == '0')
{
dark = true;
break;
}
if(!dark) res = min(res,step);
memcpy(g,backup,sizeof g);// Get the data back from the backup
}
if(res > 6) res = -1;//res = -1 Represents no solution
cout << res << endl;
}
return 0;
}
边栏推荐
- 如何用MOS管来实现电源防反接电路
- Preliminary study on temporal database incluxdb 2.2
- Used on windows Bat file startup project
- Linear algebra 1.1
- JVM中堆概念
- Wechat has new functions, and the test is started again
- zabbix监控系统部署
- Tri des fonctions de traitement de texte dans MySQL, recherche rapide préférée
- Easy to understand: understand the time series database incluxdb
- How to use C language code to realize the addition and subtraction of complex numbers and output structure
猜你喜欢
This article is enough for learning advanced mysql
L1-027 rental (20 points)
神经网络入门(下)
【Go基础】1 - Go Go Go
Heap concept in JVM
How to send mail with Jianmu Ci
[real case] how to deal with the failure of message consumption?
墨者学院-PHPMailer远程命令执行漏洞溯源
ZABBIX monitoring system custom monitoring content
Ecole bio rushes to the scientific innovation board: the annual revenue is 330million. Honghui fund and Temasek are shareholders
随机推荐
With excellent strength, wangchain technology, together with IBM and Huawei, has entered the annual contribution list of "super ledger"!
Leetcode(215)——数组中的第K个最大元素
Introduction to sap commerce cloud B2B organization function
Rapidjson reading and writing JSON files
L1-021 important words three times (5 points)
How to set multiple selecteditems on a list box- c#
如何用MOS管来实现电源防反接电路
[Gurobi] 简单模型的建立
运动【跑步 01】一个程序员的半马挑战:跑前准备+跑中调整+跑后恢复(经验分享)
In the era of low code development, is it still needed?
Zephyr study notes 2, scheduling
弈柯莱生物冲刺科创板:年营收3.3亿 弘晖基金与淡马锡是股东
Unity write word
Système de surveillance zabbix contenu de surveillance personnalisé
This article is enough for learning advanced mysql
ZABBIX monitoring system deployment
How to use MOS tube to realize the anti reverse connection circuit of power supply
Scanf read in data type symbol table
The cloud native programming challenge ended, and Alibaba cloud launched the first white paper on application liveliness technology in the field of cloud native
Blog stop statement