当前位置:网站首页>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;
}
边栏推荐
- Blog stop statement
- Sports [running 01] a programmer's half horse challenge: preparation before running + adjustment during running + recovery after running (experience sharing)
- Take you to master the formatter of visual studio code
- Is l1-029 too fat (5 points)
- L1-025 positive integer a+b (15 points)
- Used on windows Bat file startup project
- Div hidden in IE 67 shows blank problem IE 8 is normal
- PCIe knowledge points -010: where to get PCIe hot plug data
- How to write a summary of the work to promote the implementation of OKR?
- 深入浅出:了解时序数据库 InfluxDB
猜你喜欢
Oceanbase is the leader in the magic quadrant of China's database in 2021
Système de surveillance zabbix contenu de surveillance personnalisé
PCIe knowledge points -010: where to get PCIe hot plug data
The cloud native programming challenge ended, and Alibaba cloud launched the first white paper on application liveliness technology in the field of cloud native
Unity opens the explorer from the inspector interface, selects and records the file path
Flask 常用组件
L2-013 red alarm (C language) and relevant knowledge of parallel search
1、卡尔曼滤波-最佳的线性滤波器
Node foundation ~ node operation
[test de performance] lire jmeter
随机推荐
zabbix监控系统部署
I was pressed for the draft, so let's talk about how long links can be as efficient as short links in the development of mobile terminals
[test de performance] lire jmeter
How to send mail with Jianmu Ci
Go learning notes - constants
With excellent strength, wangchain technology, together with IBM and Huawei, has entered the annual contribution list of "super ledger"!
真空介电常数和真空磁导率究竟是由什么决定的?为何会存在这两个物理量?
This monitoring system can monitor the turnover intention and fishing all, and the product page has 404 after the dispute appears
Zephyr learning notes 1, threads
21 examples of strategic goals to promote the rapid development of your company
Write a thread pool by hand, and take you to learn the implementation principle of ThreadPoolExecutor thread pool
L1-030 one gang one (15 points)
[network security] what is emergency response? What indicators should you pay attention to in emergency response?
Detailed introduction to the big changes of Xcode 14
zabbix监控系统自定义监控内容
ZABBIX 5.0 monitoring client
Convert datetime string to datetime - C in the original time zone
[performance test] read JMeter
Example analysis of C # read / write lock
Système de surveillance zabbix contenu de surveillance personnalisé