search

1, Eight queens Checker Challenge

One of the following 6 \times 66 × In the checkers board of 6, 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 2 \ 4 \ 6 \ 1 \ 3 \ 5. The second number indicates that there is a chess piece in the corresponding position of line ii, as follows:

Line No.: 1 \ 2 \ 3 \ 4 \ 5 \ 6 1 2 3 4 5 6

Column No.: 2 \ 4 \ 6 \ 1 \ 3 \ 5 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 33 solutions. The last line is the total number of solutions.

Input format

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.

Input and output samples

Enter #1

6

Output #1

2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4

source code

#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
int a[20],b[20],c[20],d[40],n,k=0;
void dfs(int step)
{
	int i,j,flag;
	if(step==n)
	{
		if(k<=2)
		{
		  for(i=0;i<n;i++)
			  cout<<b[i]<<' ';
		  cout<<endl;
		  }
		  k++;
		return;
	}
	for(j=0;j<n;j++)
	{
		flag=0;
		  if(a[j]==1)
			  flag=1;
	  if(c[step+j]==1)
		  flag=1;
	  if(d[j+n-step]==1)
		  flag=1;
	  if(flag==0)
	  {
		a[j]=1;
		b[step]=j+1;
		c[step+j]=1;
		d[j+n-step]=1;
		dfs(step+1);
		a[j]=0;
		b[step]=0;
		c[step+j]=0;
		d[j+n-step]=0;
	  }
	}
	return;
}
int main()
{
	cin>>n;
	dfs(0);
	cout<<k;
}

Summary

The main thing is to control the number of outputs. More than three parts are not output, but the total number of outputs is still increasing. The second is to control the expression of rows and columns, because we should find out whether there are chess pieces in horizontal and vertical rows and oblique directions.

Traversal of horses

There is an n × On the chessboard of m, there is a horse at a certain point (x, y)(x,y). You are required to calculate the minimum steps for the horse to reach any point on the chessboard.

Input format

Enter only one line of four integers, n, m, x, yn,m,x,y.

Output format

An n × The matrix of m represents the minimum steps for the horse to reach a certain point (left aligned, 5 grids wide, output - 1 − 1 if it cannot reach).

Input and output samples

Enter #1

3 3 1 1

output

0 3 2
3 -1 1
2 1 4

## FLowchart

We will still support it flowchart Flow chart of:
```mermaid
flowchat
st=>start: start
e=>end: end
op=>operation: My operation
cond=>condition: Confirm?

st->op->cond
cond(yes)->e
cond(no)->op

code

#include<iostream>
#include<algorithm>
using namespace std;
struct step{
	int x;
	int y;
}a[160010];
int n,m,sx,sy,xx,yy,tu[401][401],nxt[8][2]={{1,2},{1,-2},{-1,2},{-1,-2},{2,1},{2,-1},{-2,1},{-2,-1}};
int main()
{
	int i,j;
	cin>>n>>m>>sx>>sy;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			tu[i][j]=-1;
	tu[sx][sy]=0;
	int head,tail;
	head=0,tail=1;
	a[tail].x=sx;
	a[tail].y=sy;
	int step;
	while(head<tail)
	{
		head++;
		step=tu[a[head].x][a[head].y]+1;
		for(i=0;i<8;i++)
		{
			xx=a[head].x+nxt[i][0];
			yy=a[head].y+nxt[i][1];
			if(tu[xx][yy]==-1&&xx<=n&&yy<=m&&xx>=1&&yy>=1)
			{
				tail++;
				a[tail].x=xx;
				a[tail].y=yy;
				tu[xx][yy]=step;
			}
		}
	}
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			printf("%-5d",tu[i][j]);
		}
		cout<<endl;
	}
}

Summary

First mark the whole area as - 1, and then use BFS to search. After the search, directly output the whole array