奇偶交错排列(DFS)

Description

一个1-n1−n的排列满足所有相邻数字奇偶性不同，那么称该排列为奇偶交错排列。

按字典序输出1-n1−n的所有奇偶交错排列。

Input

输入一个整数n( 2 \le n \le 11)n(2≤n≤11)

Output

输出若干行，每行一个排列。相邻数字之间以一个空格分隔，行末无空格。

请严格按照输出格式，输出不规范将直接判成Wrong answer

Sample Input 1

Sample Output 1

代码：

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

using namespace std;

int n;

int a[15];

int vis[15];

void dfs(int x,int dig)

{

	a[dig]=x;

	if(dig==n-1)

	{

	for(int t=0;t<n;t++)

	{

		if(t!=0)

		printf(" %d",a[t]);

		if(t==0)

		printf("%d",a[t]);

	}

	cout<<endl;

	return ;

	}

	if(x%2==1)

	{

	  for(int t=1;t<=n;t++)

	  {

	  	if(t%2==0&&vis[t]==0)

	  	{

	  		vis[t]=1;

	  		dfs(t,dig+1);

	  		vis[t]=0;

		}

	  }

	}

	if(x%2==0)

	{

		for(int t=1;t<=n;t++)

	  {

	  	if(t%2==1&&vis[t]==0)

	  	{

	  		vis[t]=1;

	  		dfs(t,dig+1);

	  		vis[t]=0;

		}

	  }

	}

}

int main()

{

	cin>>n;

	for(int t=1;t<=n;t++)

	{

		vis[t]=1;

		dfs(t,0);

		vis[t]=0;

	}

}

巴特西

奇偶交错排列(DFS)

最新文章

热门文章