当前位置:网站首页>Acwing-116 pilot brother
Acwing-116 pilot brother
2022-07-06 12:35:00 【Want no boat at the bottom of the sea】
The essence of this problem is the same as that of eight digits
First define a state
struct st{
int map[4];// Handle status
int num;// They count
vector<int> s;// route
int a;// ID code
}
About the steps
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define x first
#define y second
using namespace std;
// Defining structure
struct st {
};
st bfs() {
// initialization
queue<st> que;
que.push();
while () {
st t = que.front();
for()
for () {
// Make new elements
if()// End the process when the conditions are met ;
return
}
que.pop()// Delete the head element
}
}
int main() {
// receive data
for (.....) cin >> ...//
// Make the header element
bfs();// Output results
}
The actual code
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define x first
#define y second
using namespace std;
const int N = 5;
int n = 4;
bool jud[1000000];
typedef pair<int, int> two;
struct st {
int map[N][N];
int num;
int a;
vector<two> s;
}st1;
void clone(int a[][N], int b[][N]) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++)
a[i][j] = b[i][j];
}
}
void change(int x, int y, int mid[][N]) {
for (int i = 1; i <= n; i++)
mid[i][y] = mid[i][y] ^ 1;
for (int i = 1; i <= n; i++)
mid[x][i] = mid[x][i] ^ 1;
mid[x][y] = mid[x][y] ^ 1;
}
int make(int a[][N]) {
int sum = 0, fur = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++)
if (a[i][j]) sum += 1 << fur++;
else fur++;
}
return sum;
}
st bfs() {
queue<st> que;
que.push(st1);
while (que.size()) {
st t = que.front();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if(t.s.size())
if (i == t.s.back().x&&j == t.s.back().y)
continue;
st mid;
clone(mid.map, t.map);//map
change(i, j, mid.map);
mid.a = make(mid.map);//a
if (!jud[mid.a]) {
jud[mid.a] = true;
mid.num = t.num + 1;//num
mid.s = t.s;//s
mid.s.push_back({ i,j });
que.push(mid);
if (mid.a == 65535) {
cout << mid.num << endl;
return mid;
}
}
}
}
que.pop();
}
}
int main() {
for(int i=1;i<=n;i++)
for (int j = 1; j <= n; j++) {
char a; cin >> a;
if (a == '-') st1.map[i][j] = 1;
else st1.map[i][j] = 0;
}
st1.a = make(st1.map);
jud[st1.a] = 1;
st1.num = 0;
st it = bfs();
for (int i = 0; i < it.s.size(); i++)
cout << it.s[i].x << ' ' << it.s[i].y << endl;
}
边栏推荐
- 1081 rational sum (20 points) points add up to total points
- Expected value (EV)
- [Clickhouse kernel principle graphic explanation] about the collaborative work of partitioning, indexing, marking and compressed data
- Who says that PT online schema change does not lock the table, or deadlock
- Redis based distributed ID generator
- Talking about the startup of Oracle Database
- (三)R语言的生物信息学入门——Function, data.frame, 简单DNA读取与分析
- [leetcode19] delete the penultimate node in the linked list
- Esp8266 connects to bafayun (TCP maker cloud) through Arduino IED
- JS数组常用方法的分类、理解和运用
猜你喜欢
There is no red exclamation mark after SVN update
Basic operations of databases and tables ----- view data tables
Idea problem record
Unity场景跳转及退出
Classification, understanding and application of common methods of JS array
Fashion Gen: the general fashion dataset and challenge paper interpretation & dataset introduction
js 变量作用域和函数的学习笔记
idea问题记录
Force buckle 1189 Maximum number of "balloons"
[Clickhouse kernel principle graphic explanation] about the collaborative work of partitioning, indexing, marking and compressed data
随机推荐
History object
ES6 grammar summary -- Part 2 (advanced part es6~es11)
By v$rman_ backup_ job_ Oracle "bug" caused by details
Arduino JSON data information parsing
Common DOS commands
MySQL takes up too much memory solution
MySQL时间、时区、自动填充0的问题
Gravure sans fil Bluetooth sur micro - ordinateur à puce unique
1041 Be Unique (20 point(s))(哈希:找第一个出现一次的数)
ESP8266连接onenet(旧版MQTT方式)
Programmers can make mistakes. Basic pointers and arrays of C language
Basic operations of databases and tables ----- modifying data tables
Unity3D制作注册登录界面,并实现场景跳转
Teach you to release a DeNO module hand in hand
[Nodejs] 20. Koa2 onion ring model ----- code demonstration
Working principle of genius telephone watch Z3
Arm pc=pc+8 is the most understandable explanation
NRF24L01 troubleshooting
[leetcode622]设计循环队列
JUC forkjoin and completable future