P1219 eight queens Checker Challenge
Eight queens Checker Challenge
Title Description
For a checkers board of 6 * 6 as follows, six pieces are placed on the board so that there is and only one piece in each row and column, and there is at most one piece on each diagonal (including all parallel lines of the two main diagonals).
The above layout can be described by sequence 2 4 6 1 3 5. The i-th number indicates that there is a chess piece at the corresponding position of line I, as follows:
Line No. 1 2 3 4 5 6
Train No. 2 4 6 1 3 5
This is just a solution to the placement of chess pieces. Please make a program to find out the solution of all pieces.
And output them in the above sequence method, and the solutions are arranged in dictionary order.
Please output the first 3 solutions. The last line is the total number of solutions.
[data range]
For 100% data, 6 ≤ n ≤ 13.
Input format
A positive integer n in a line indicates that the chessboard is n × N size.
Output format
The first three lines are the first three solutions, and the two numbers of each solution are separated by a space. The fourth line has only one number, indicating the total number of solutions.
sample input
6
sample output
2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4
Problem solution
The eight queens problem is a classic search problem. It is required to find the number of all solutions. Obviously, or think of using the backtracking method, recursively traverse the whole chessboard, mark the qualified positions, and then recurse to the next level to get the corresponding solution. The following is a template for backtracking.
void backtracking(parameter) {
if (Termination conditions) {
Storage results;
return;
}
for (Selection: Elements in the collection of this layer (the number of node children in the tree is the size of the collection)) {
Processing node;
backtracking(Path, selection list); // recursion
Backtracking, undo processing results
}
}
The code is as follows:
#include<iostream>
using namespace std;
#define maxn 100
int a[maxn], b[maxn], c[maxn], d[maxn];
//Four arrays are used to represent rows, columns, primary diagonals and their parallel lines (i + j are the same), secondary diagonals and their parallel lines (i - j are the same)
int ans = 0, n;
void show() {
for (int i = 1; i <= n; i++) {
cout << a[i] << " ";
}
cout << endl;
}
void search(int i) {
if (i > n) {
if (ans < 3)
show();
ans++;
return;
}
for (int j = 1; j <= n; j++) {
if (!b[j] && !c[i + j] && !d[i - j + n]) {
a[i] = j;
b[j] = 1;
c[i + j] = 1;
d[i - j + n] = 1;
search(i + 1);
b[j] = 0;//to flash back
c[i + j] = 0;
d[i - j + n] = 0;
}
}
}
int main() {
cin >> n;
search(1);
cout << ans;
return 0;
}
P1123 data access game
Title Description
An N × For the number matrix composed of non negative integers of M, you need to take out several numbers so that any two numbers taken out are not adjacent (if a number is adjacent to another number in one of the 88 grids, it is considered that the two numbers are adjacent), and find out the maximum sum of the numbers taken out.
For 100% 100% data, N, M ≤ 6, T ≤ 20.
Input format
The first line has a positive integer T, which indicates that there are t groups of data.
For each set of data, the first row has two positive integers N and M, indicating that the digital matrix is N rows and M columns.
Next, N rows, M nonnegative integers per row, describe the numeric matrix.
Output format
Line T, a non negative integer in each line, outputs the obtained answer.
sample input
3
4 4
67 75 63 10
29 29 92 14
21 68 71 56
8 67 91 25
2 3
87 70 85
10 3 17
3 3
1 1 1
1 99 1
1 1 1
sample output
271
172
99
Problem solution
This is a simple topic of dfs. To get the maximum value of several non adjacent numbers, you can get the maximum value every time you traverse the array. The maximum value obtained each time is compared by using the backtracking mark method to get the final answer
The code is as follows:
#include<iostream>
using namespace std;
int N, M;
#define maxn 100
int a[maxn][maxn];
int vis[maxn][maxn];
int ans = 0;
void dfs(int x, int y, int value) {
if (x > N) {//If the entire matrix is searched, the maximum value is replaced
ans = max(ans, value);
return;
}
int nextx = x, nexty = y + 1;
if (nexty > M) {//If the column is out of range, replace the next row
nextx = x + 1, nexty = 1;
}
if (!vis[x - 1][y] && !vis[x][y - 1] && !vis[x - 1][y - 1] && !vis[x - 1][y + 1]) {//Judgment conditions
vis[x][y] = 1;
dfs(nextx, nexty, value + a[x][y]);
vis[x][y] = 0;//to flash back
}
dfs(nextx, nexty, value);//If you don't take this number
}
int main() {
int T;
cin >> T;
while (T--) {
ans = 0;
cin >> N >> M;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
cin >> a[i][j];
}
}
dfs(1, 0, 0);
cout << ans << endl;
}
}
P1135 strange elevator
Problem solution
It is required to obtain the minimum number of keys in the question. It can be seen that this is a simple bfs search question. It can traverse the upstairs or downstairs of each floor, and judge whether it can reach the corresponding floor according to the final result
The code is as follows:
#include<iostream>
#include<queue>
using namespace std;
int n, a, b;
#define maxn 1000
bool vis[maxn];
int button[maxn];
int ans = 0;
struct node {
int floor;
int step;
};
node bfs(node p) {
queue<node> q;
q.push(p);
vis[p.floor] = 1;
node x;
while (!q.empty()) {
x = q.front();
q.pop();
if (x.floor == b) {
return x;
} else {
node next;
next.step = x.step + 1;
if (x.floor + button[x.floor] <= n && !vis[x.floor + button[x.floor]]) {
next.floor = x.floor + button[x.floor];
q.push(next);
vis[next.floor] = 1;
}
if (x.floor - button[x.floor] >= 1 && !vis[x.floor - button[x.floor]]) {
next.floor = x.floor - button[x.floor];
q.push(next);
vis[next.floor] = 1;
}
}
}
return x;
}
int main() {
cin >> n >> a >> b;
for (int i = 1; i <= n; i++) {
cin >> button[i];
}
node p;
p.floor = a, p.step = 0;
node t = bfs(p);
if (t.floor == b) cout << t.step << endl;
else cout << -1 << endl;
}
P3958 cheese
Problem solution
Use dfs to search each hole and exit if it meets the conditions. Compared with bfs breadth search, dfs will run less data and faster in this problem
The AC code is as follows:
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn = 1010;
struct cir {
double x, y, z;
bool operator<(const cir &cpr) const {
return z < cpr.z;
}
} p[maxn];
bool fnd = 0;
int n;
double h, r;
bool vis[maxn];
double dist(double x1, double y1, double z1, double x2, double y2, double z2) {
return sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) + (z2 - z1) * (z2 - z1));
}
void dfs(cir now, int num) {
if (now.z + r >= h) {
fnd = 1;
return;
}
vis[num] = 1;
for (int i = 1; i <= n; i++) {
if (fnd)
return;
if (!vis[i] && dist(now.x, now.y, now.z, p[i].x, p[i].y, p[i].z) <= r * 2)
dfs(p[i], i);
}
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
memset(vis, 0, sizeof(vis));
memset(p, 0, sizeof(p));
fnd = 0;
scanf("%d%lf%lf", &n, &h, &r);
for (int i = 1; i <= n; i++)
scanf("%lf%lf%lf", &p[i].x, &p[i].y, &p[i].z);
std::sort(p + 1, p + n + 1);
for (int i = 1; i <= n; i++)//lower
if (p[i].z - r <= 0)
dfs(p[i], i);
if (fnd)
puts("Yes");
else
puts("No");
}
return 0;
}
P1443 traversal of horses
Problem solution
The typical bfs entry problem is very shameful. Recently, I am used to MATLAB. The for loop of bfs child node uses indentation instead of parentheses by default, and has been debugged for a long time
The AC code is as follows:
#include <cstdio>
#include <string.h>
#include <cmath>
#include <queue>
using namespace std;
struct node {
int x, y;
int step;
};
const int xx[8] = {1, 1, -1, -1, 2, 2, -2, -2};
const int yy[8] = {2, -2, 2, -2, 1, -1, 1, -1};
#define maxn 405
int a[maxn][maxn];
bool vis[maxn][maxn];
int n, m;
void bfs(node p) {
a[p.x][p.y] = p.step;
queue<node> q;
q.push(p);
vis[p.x][p.y] = 1;
while (!q.empty()) {
node x = q.front();
node next;
q.pop();
for (int i = 0; i < 8; i++) {
next.x = x.x + xx[i], next.y = x.y + yy[i], next.step = x.step + 1;
if (next.x >= 1 && next.x <= n && next.y >= 1 && next.y <= m && !vis[next.x][next.y]) {
q.push(next);
vis[next.x][next.y] = 1;
a[next.x][next.y] = next.step;
}
}
}
}
int main() {
memset(vis, false, sizeof(vis));
memset(a, -1, sizeof(a));
int x, y;
scanf("%d%d%d%d", &n, &m, &x, &y);
node p;
p.x = x, p.y = y, p.step = 0;
bfs(p);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++)
printf("%-5d", a[i][j]);
printf("\n");
}
return 0;
}
acwing 845. Eight digital
Problem solution
Eight digit should be the most difficult problem encountered today. Different from the intuitive search of the above problem, eight digit needs to convert the target object, convert the image into a string, and judge whether the strings are equal
The AC code is as follows:
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
using namespace std;
int bfs(string start)
{
//Define target status
string end = "12345678x";
//Define queues and dist arrays
queue<string> q;
unordered_map<string, int> d;
//Initialize queue and dist array
q.push(start);
d[start] = 0;
//Transfer mode
int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
while(q.size())
{
auto t = q.front();
q.pop();
//Record the distance of the current state. If it is the final state, return the distance
int distance = d[t];
if(t == end) return distance;
//Query the subscript of x in the string and convert it to the coordinates in the matrix
int k = t.find('x');
int x = k / 3, y = k % 3;
for(int i = 0; i < 4; i++)
{
//Find the coordinates of x after transfer
int a = x + dx[i], b = y + dy[i];
//The current coordinates are not out of bounds
if(a >= 0 && a < 3 && b >= 0 && b < 3)
{
//Transfer x
swap(t[k], t[a * 3 + b]);
//If the current state is the first traversal, record the distance and join the queue
if(!d.count(t))
{
d[t] = distance + 1;
q.push(t);
}
//Restore the state to prepare for the next transition
swap(t[k], t[a * 3 + b]);
}
}
}
//Unable to transition to target state, return - 1
return -1;
}
int main()
{
string c, start;
//Input start status
for(int i = 0; i < 9; i++)
{
cin >> c;
start += c;
}
cout << bfs(start) << endl;
return 0;
}